Increasing Array Solution

6 September 2021

Statement

( The original statement can be found here )
You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input
The first input line contains an integer n: the size of the array.

Then, the second line contains n integers x1,x2,…,xn: the contents of the array.

Output
Print the minimum number of moves.

Constraints
1 ≤ n ≤ 2x\(10^5\)
1 ≤ \(x_i\) ≤ \(10^9\)
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
5
3 2 5 1 7

Output :
5

Solution

What is the optimal strategy to this problem ? In other words what is the minimum number of operations required so that for any \(i>0\), \(\:A[i] \geq A[i-1]\).

To better understand the solutionm, it is probably better to think of the array as a mountain, where each value represents either the height of a peak or a valley.
(The following image represents the sample input).

The question now becomes, what is the minimum amount of change such that the mountain never goes down. And it should now be clear that all we have to do is get rid of the valleys by moving the appropriate indices.

We can simply iterate through the array and if \(A[i] \leq A[i-1]\) we increment the \(answer\) by \(A[i-1] - A[i]\) since this is the minimum number of moves to make them equal. Finally, we update \(A[i]\) to \(A[i]+(A[i-1]-A[i])\) and we get the optimal strategy.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, x, answer = 0;
    cin >> n;
    long long values[n];
    for (int i = 0; i < n; i++) {
        cin >> values[i];
    }
    for (int i = 1; i < n; i++) {
        if (values[i] < values[i - 1]) {
            answer += (values[i - 1] - values[i]);
            values[i] = values[i - 1];
        }
    }
    cout << answer;
}

Since we only have \(N\) numbers and iterate through them once, we get a time and space complexity of \(O(N)\).