Minimum no of changes required to make array strictly increasing

Question

I have a problem in which we have an array of positive numbers and we have to make it strictly increasing by making zero or more changes to the array elements.

We are asked the minimum number of changes required to make the array strictly increasing.

Example

if array is 1 2 9 10 3 15

so ans=1 if change 3 to some number between 12 to 14.

if 1 2 2 2 3 4 5

ans=5

since changing 2 to 3 then 2 to 4 then 3 to 5 then 4 to 6 then 5 to 7

Constraints:

Number of elements in array <= 10^6

Each element <= 10^9

Can somebody give me an algorithm?

Link to the detailed problem with sample test cases https://www.hackerearth.com/problem/algorithm/find-path/

Since it is mini/max problem, it sounds like dynamic programming to me, but I'm not sure.

Answer 1

HINT 1

This is very close to the standard longest increasing subsequence problem which is solvable in O(nlogn).

If you could change the numbers to decimals then the answer would be identical. (Min number of changes = length of string-length of longest increasing subsequence)

However, as you need distinct integral values in between you will have to slightly modify the standard algorithm.

HINT 2

Consider what happens if you change the array by doing x[i]=x[i]-i.

You now need to modify this changed array by making the smallest number of changes such that each element increases, or stays the same.

You can now search for the longest non-decreasing subsequence in this array and this will tell you how many elements can stay the same.

However, this may still use negative integers.

HINT 3

One easy way to modify the algorithm to only use positive numbers is to append a whole lot of numbers at the start of the array.

i.e. change 1,2,9,10,3,15 to -5,-4,-3,-2,-1,1,2,9,10,3,15

Then you can be sure that the optimal answer will never decide to make the 1 go negative because it would cost so much to make all the negative numbers smaller.

(You can also modify the longest increasing subsequence algorithm to have the additional constraint, but this might be harder to code correctly in an interview situation.)

EXAMPLE 1

Following this through on the initial example:

Original sequence

1,2,9,10,3,15

Add dummy elements at start

-5,-4,-3,-2,-1,1,2,9,10,3,15

Subtract off position in array

-5,-5,-5,-5,-5,-4,-4,2,2,-6,5

Find longest non-decreasing sequence

-5,-5,-5,-5,-5,-4,-4,2,2,*,5

So answer is to change one number.

EXAMPLE 2

Original sequence

1,2,2,2,3,4,5

Add dummy elements at start

-5,-4,-3,-2,-1,1,2,2,2,3,4,5

Subtract off position in array

-5,-5,-5,-5,-5,-4,-4,-5,-6,-6,-6,-6

Find longest non-decreasing sequence

-5,-5,-5,-5,-5,-4,-4,*,*,*,*,*

So answer is to change 5 numbers.