Minimum no. of operations to make array strictly increasing

Revision en1, by Lakh, 2021-06-13 05:24:14
An array of length N is given . In one operation we can increment/decrement any array element. We have to find minimum no. of such operations to make array strictly increasing.

For e.g. N = 5
         5 4 3 2 1
         Ans: 12

I tried this problem using concept known as Slope trick where first we convert all array elements in following fashion : A[i] = A[i] — i;

After this I tried finding LIS of new sequence and then updating the elements which are not a part of LIS. However, there may be multiple LIS sequences present in the tranformed array. In that case how to decide which sequence to take.

Also let me know if my approach is correct or if any other approach is there to solve this task. Thanks in advance :)

Tags array, minimization, slope trick


  Rev. Lang. By When Δ Comment
en1 English Lakh 2021-06-13 05:24:14 836 Initial revision (published)