How to convert an array into a strictly increasing array?
Difference between en1 and en2, changed 16 character(s)
This is a problem from a past hiring contest of Hackerrank.↵
We are given an array which contains at max 10^4 elements.↵
Total cost is defined as the sum of absolute difference of the old value of the element and the new value of the element.↵
↵
Ex: 10 6 3 2 2000↵
↵
↵
Minimum Cost: 11↵
↵
1st element 10 can be changed to 6. Cost = abs(10 — 6) = 4.↵
↵
3rd element 3 can be changed to 6. Cost = abs(3 — 6) = 3.↵
↵
4th element 2 can be changed to 6. Cost = abs(2 — 6) = 4.↵
↵
So total cost = 11↵
↵
↵
Range of elements: [1, 10^9]↵
↵
How can I apply dynamic programming to solve it?↵
Thanks :-) 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English codemode 2019-06-19 20:08:31 16
en1 English codemode 2019-06-19 20:04:25 650 Initial revision (published)