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 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 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