Some error occured while loading page for you. Please try again.

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