You have an array of integers.

In one step, you can change the value at an index into any integer value. What is the minimum number of steps in which you can make the array non-decreasing?

Eg 1:

If the array is [8, 12, 11, 15],

We can change the value at the index 2 from 11 to 13. Then the array becomes [8, 12, 13, 15]

So, no of steps needed = 1;

Eg 2:

If the array is [9, 2, 5, 18, 20, 25, 19],

We can change the value at the index 0 from 9 to 2 and the value at the index 6 from 19 to 30. Then the array becomes [2, 2, 5, 18, 20, 25, 30]

So, no of steps needed = 2;

Eg 3:

If the array is [9, 11, 5, 7],

We can change the value at the index 2 from 5 to 11 and the value at the index 3 from 7 to 11. Then the array becomes [9, 11, 11, 11]

So, no of steps needed = 2;

Eg 4:

If the array is [13, 12, 10, 7, 6],

After making the changes, the array becomes [13, 13, 13, 13, 13] or [6, 7, 10, 12, 13]. There are ways of doing this.

So, no of steps needed = 4;

One way I tried would be to find all the decreasing subsequences and add the length of them -1 to a variable named ans. Then return it. But it's failing in the Eg 3 mentioned above. How to solve this?

CodePudding user response：

I think this problem is equivalent to finding the longest non-decreasing chain in the sequence.

Take each index i to be the node of a graph. Then node i has an arrow to node j if and only if i < j and L[i] <= L[j]. Then you need to find the longest path in the graph using techniques from graph theory.

You won't get loops because of the condition i<j.

CodePudding user response：

As @sfx mentions, this is equivalent to finding the longest non-decreasing subsequence. You can find the length of this subsequence using Patience sorting.

The algorithm from Wikipedia:

1. The first card dealt forms a new pile consisting of the single card.
2. Each subsequent card is placed on some existing pile whose top card has a value no less than the new card's value, or to the right of all of the existing piles, thus forming a new pile.
3. When there are no more cards remaining to deal, the game ends.

Using your example 3:

[9, 11, 5, 7]

Insert [9]:

[9]

Insert [11]: There is no value greater than or equal to [11] in the output array, so add another stack:

[9, 11]

Insert [5]: The first value greater than or equal to [5] is [9], so replace [9]:

[5, 11]

Insert [7]: The first value greater than or equal to [7] is [11], replace [11]:

[5, 7]

The length of the output array is the length of the longest non-decreasing subsequence. The number of operations to make the entire sequence non-decreasing is equal to the number of elements in the input array minus the length of this subsequence.

Using binary search to determine where to place the next value, the worst case time complexity of this approach is O(n log n).