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 believe what he's trying to say is this:
There are two approaches here -
1. The difference array approach (the one every one is praising as being more efficient)
2. The intuitive approach - i.e., just going through each group of a,b,k values and incrementing elements located between a and b in the array, then finally searching through for a max)

The reason approach 1 is more efficient is because the operation for the difference array only requires a maximum 2 adjustments per transformation (you increment the value at the start index by k, and decrement the value after the end index by k).
Contrast this with approach 2, where actually going through the array and incrementing every value within the specified 'a-b' range could result in N operations.

So approach 2 could take a max of O(N * M) time- where 'M' is the number of operations, and N is the size of the array
And approach 1 could take a max of O(2 * M) time, which is considered equivalent to O(M)

Does that make sense? Someone correct me if I'm wrong! Cheers :)

the best way to understand it is form a simple example.

say there are 4 of us in a line: 1. me 2. you 3. bob 4. sue
and we all start out with zero points.

Thcan be represented as (where my points are in the first index, your in the second, bob's in the third, sue's in fourth):

0 0 0 0

Furthermore, we go through rounds, where in each round a contiguous block of us can receive some set amount of points.

So in round one, say 2 points are awarded to anything in the range of start index = 1, and end index = 2. This means that you and bob, who are in the range, get 2 points.

But rather than write the current score as:
0 2 2 0

We instead want to write the score as:

0 2 0 -2

Because we want each value to represent how much greater/less than it is from the previous-index value. Doing this allows us to only ever need to change two elements in the list for a given round.

Now say we play one more round, and 1 point is awarded to all people in range of index = 0 to index = 1. This gives you

1 2 -1 -2

All I did was add the point value to the start index, and subtract it from the "end index + 1".

Then calculating the max is simply a matter of going through that list, adding each element to an accumulator variable (as this summing process reveals the actual value of an element at any given point - e.g., you would have 3 points at the end because your score is the result of 1 + 2), and having a variable which keeps track of the running max.

## Array Manipulation

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

I believe what he's trying to say is this: There are two approaches here - 1. The difference array approach (the one every one is praising as being more efficient) 2. The intuitive approach - i.e., just going through each group of a,b,k values and incrementing elements located between a and b in the array, then finally searching through for a max)

The reason approach 1 is more efficient is because the operation for the difference array only requires a maximum 2 adjustments per transformation (you increment the value at the start index by k, and decrement the value after the end index by k). Contrast this with approach 2, where actually going through the array and incrementing every value within the specified 'a-b' range could result in N operations.

So approach 2 could take a max of O(N * M) time- where 'M' is the number of operations, and N is the size of the array And approach 1 could take a max of O(2 * M) time, which is considered equivalent to O(M)

Does that make sense? Someone correct me if I'm wrong! Cheers :)

Yeah, if we went with the brute force solution with two nested for loops, we will get a graph as below for the array if we used the data below

but if we used the second method which is adding at the first index and subtracting at the index afer the last we get this graph

and then we can get the maximum out of summing the results as below

but I can't understand the logic of least step ( summing step )

the best way to understand it is form a simple example.

say there are 4 of us in a line: 1. me 2. you 3. bob 4. sue and we all start out with zero points.

Thcan be represented as (where my points are in the first index, your in the second, bob's in the third, sue's in fourth):

0 0 0 0

Furthermore, we go through rounds, where in each round a contiguous block of us can receive some set amount of points.

So in round one, say 2 points are awarded to anything in the range of start index = 1, and end index = 2. This means that you and bob, who are in the range, get 2 points.

But rather than write the current score as: 0 2 2 0

We instead want to write the score as:

0 2 0 -2

Because we want each value to represent how much greater/less than it is from the previous-index value. Doing this allows us to only ever need to change two elements in the list for a given round.

Now say we play one more round, and 1 point is awarded to all people in range of index = 0 to index = 1. This gives you

1 2 -1 -2

All I did was add the point value to the start index, and subtract it from the "end index + 1".

Then calculating the max is simply a matter of going through that list, adding each element to an accumulator variable (as this summing process reveals the actual value of an element at any given point - e.g., you would have 3 points at the end because your score is the result of 1 + 2), and having a variable which keeps track of the running max.

Thank you for your detailed explanation. It helped!

This is the best explanation of the difference array I have read in these discussions -- thank you for making it click in my head.