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.
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.
Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)
I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.
Here is the video tutorial for my solution O(n+m) complexity passed all test cases.
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
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.
Hi,
Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)
I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.
Here is the video tutorial for my solution O(n+m) complexity passed all test cases.
https://youtu.be/hDhf04AJIRs
Would really appreciate your feedback like, dislike , comment etc. on my video.