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.
After contemplating the popular approach for solving this, here is how I wrapped my head around it.
For every input line of a-b-k, you are given the range (a to b) where the values increase by k. So instead of keeping track of actual values increasing, just keep track of the rate of change (i.e. a slope) in terms of where the rate started its increase and where it stopped its increase. This is done by adding k to the "a" position of your array and adding -k to the "b+1" position of your array for every input line a-b-k, and that's it. "b+1" is used because the increase still applied at "b".
The maximum final value is equivalent to the maximum accumulated "slope" starting from the first position, because it is the spot which incremented more than all other places. Accumulated "slope" means to you add slope changes in position 0 to position 1, then add that to position 2, and so forth, looking for the point where it was the greatest.
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
After contemplating the popular approach for solving this, here is how I wrapped my head around it.
For every input line of a-b-k, you are given the range (a to b) where the values increase by k. So instead of keeping track of actual values increasing, just keep track of the rate of change (i.e. a slope) in terms of where the rate started its increase and where it stopped its increase. This is done by adding k to the "a" position of your array and adding -k to the "b+1" position of your array for every input line a-b-k, and that's it. "b+1" is used because the increase still applied at "b".
The maximum final value is equivalent to the maximum accumulated "slope" starting from the first position, because it is the spot which incremented more than all other places. Accumulated "slope" means to you add slope changes in position 0 to position 1, then add that to position 2, and so forth, looking for the point where it was the greatest.