We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

I came out with the same approach in java, but code is ridiculously larger :P

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* Created by juanmf on 08/02/17.
*/
public class AlgorihmicCrush {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int M = s.nextInt();
//int[] operations = new int[N + 1];
List<Long>[] operations = new List[N + 1];
while (s.hasNextInt()) {
int from = s.nextInt();
int to = s.nextInt();
long sum = s.nextLong();
addOperation(operations, from, to, sum);
}
System.out.println(copmileOperations(operations));
}
private static long copmileOperations(List<Long>[] operations) {
long crawler = 0;
long max = Integer.MIN_VALUE;
for (List<Long> ops : operations) {
if (null == ops) {
continue;
}
for (Long op : ops) {
crawler += op;
}
if (max < crawler) {
max = crawler;
}
}
return max;
}
private static void addOperation(List<Long>[] operations, int from, int to, long sum) {
if (null == operations[from]) {
operations[from] = new ArrayList<Long>();
}
operations[from].add(sum);
to++;
if (to >= operations.length) {
return;
}
if (null == operations[to]) {
operations[to] = new ArrayList<Long>();
}
operations[to].add(-sum);
}
}

I also did it on Java. At first, it only passed up to test 3, due some precision loss, having int k instead of long k. This may be obvious to many here, but I still thought it was interesting to see how such a small detail changes it all. Here is the code (in comments, the code with int, which fails after test 3).

public static void main(String[] args) {
int N, M, a, b;
long k; // int k;
Scanner in = new Scanner(System.in);
N = in.nextInt();
M = in.nextInt();
long[] differenceArray = new long[N+1]; // int[] ...
for (int i=0; i<M; i++)
{
in.nextLine();
a = in.nextInt();
b = in.nextInt();
k = in.nextLong(); // in.nextInt();
differenceArray[a] += k;
if (b+1<=N)
differenceArray [b+1] -= k;
}
long max = 0, addedDifference = 0; // int
for (int i=1; i<=N; i++)
{
addedDifference = addedDifference + differenceArray[i];
if (max < addedDifference)
max = addedDifference;
}
System.out.println(max);
in.close();
}

Let's view the array as a list of histograms. Each position in the array has a histogram with a certain variable heigth. It would be cumbersome to keep track of the heigth of every single histogram. Instead, you could just keep track of how much the height of a given histogram differs from the one preceding it (in a continuous setting, this would mean to keep track of the derivative of a function, not the function itself).

Here, we know there is an increment of k for the height of the histogram in position a (a positive slope of k from a-1 to a), but then the height remains constant at positions a+1, a+2,...,b. Then again, we know that position b was the last position where histograms were incremented by k, so there is a decrement of -k at position b+1 (negative slope of -k from b to b+1).

## Array Manipulation

You are viewing a single comment's thread. Return to all comments →

I came out with the same approach in java, but code is ridiculously larger :P

You might want to try replacing

`List<Long>[]`

with`long[]`

. There's no reason to build all of those arraylists and aggregate them later.sounds good, thx

I also did it on Java. At first, it only passed up to test 3, due some precision loss, having int k instead of long k. This may be obvious to many here, but I still thought it was interesting to see how such a small detail changes it all. Here is the code (in comments, the code with int, which fails after test 3).

import java.io.

; import java.util.; import java.text.; import java.math.; import java.util.regex.*;public class Solution {

}

Can you explain this line

differenceArray[a] += k; if (b+1<=N) differenceArray [b+1] -= k; }

Why are you adding k to only differenceArray[a]??

Let's view the array as a list of histograms. Each position in the array has a histogram with a certain variable heigth. It would be cumbersome to keep track of the heigth of every single histogram. Instead, you could just keep track of how much the height of a given histogram differs from the one preceding it (in a continuous setting, this would mean to keep track of the derivative of a function, not the function itself).

Here, we know there is an increment of k for the height of the histogram in position a (a positive slope of k from a-1 to a), but then the height remains constant at positions a+1, a+2,...,b. Then again, we know that position b was the last position where histograms were incremented by k, so there is a decrement of -k at position b+1 (negative slope of -k from b to b+1).

Hope this helps.

you can check it out in the assumptions area. if int values can be more than 2**30 or you can have many accumulated in one int. etc..

urgh! finally I was able to understand this damned problem! thanks for your explanation @hl2kerg!

Thank you so much, I too was stuck for that small reason for hours together!! Thaks allot;)

nice

same thing happened to me ..using int instead of long