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.
Logic for the original (get all the a,b,k values loop through updating for k, then repeat for other a,b,k values) makes sense and is my go to instinct, but as you can see nested for loops mean its O(N^2).
The refined took some figuring out the logic being that A,B,K mean A through B have all the same values (an increase of K).
Therefore you do not need to loop to update through every single value.
Instead you can use 1 loop to update the specific values A and B (adjusted for 1-index). A is an increase as once you start that range of indices you gain K. B is a decrease as after you leave taht range of indices you lose K in the indices after.
Then a separate loop (not nested) to do a running sum to find the max value.
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
Logic for the original (get all the a,b,k values loop through updating for k, then repeat for other a,b,k values) makes sense and is my go to instinct, but as you can see nested for loops mean its O(N^2).
The refined took some figuring out the logic being that A,B,K mean A through B have all the same values (an increase of K). Therefore you do not need to loop to update through every single value. Instead you can use 1 loop to update the specific values A and B (adjusted for 1-index). A is an increase as once you start that range of indices you gain K. B is a decrease as after you leave taht range of indices you lose K in the indices after. Then a separate loop (not nested) to do a running sum to find the max value.
Refined Working
Original not working time complexity, nested for loops O(N^2)