Hi, I came across this problem where you are given an array a, your task is to convert it into a non-increasing form such that we can either increment or decrement the array value by 1 in minimum changes possible.
One approach that I could think of using dp where dp[i][j] stood for minimum number of changes for first i elements if we use the largest j heights in the original array.
This approach has time complexity of O(N^2) and space complexity of O(N). But there seems to be better approach as mentioned in this blog https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/. But I was neither able to understand the approach described nor the code given.
But I checked the correctness of the code in the blog against my dp code. Both of them were producing same results. So if anyone could let me know how the O(N*log(N)) solution works that would be great.
Slope trick.
Thank you so much, that helped a lot.
Wouldn't the answer to the array [1,2,3,4,5] be 6, but I think this algo given in the link will produce answer as 4. Please clarify.
It outputs 6 on custom invocation.
Yes my mistake thanks.