Minimum number of steps required to make all elements of sequence 0-CodePudding

Given a sequence of integers calculate the minimum number of operations required to make all numbers 0. An operation is of the following: Increase or decrease all numbers from index i to index j by 1.

Example 1)

{1, 1, -1}

You can do:

Decrease indices 0 to 1

Increase indices 2 to 2

So the answer is 2 operations.

Example 2)

{3, -1, -1, 3}

Decrease indices 0 to 3

Increase indices 1 to 2

So answer is 7.

What would be an efficient algorithm to do this?

CodePudding user response：

One issue is that there are many ways to get final result to 0, even with the minimum number of operations in all cases.

For example, with {1, 0, 1}, we an apply -1 on [0, 2] and 1 on [1, 1]
or we can apply -1 on [0, 0], and then -1on [2, 2].

In both cases, two operations are needed.

As only the minimum number of operations is needed, we can decide to split the operations on distinct intervals as soon as it seems not suboptimal.

Then, an iterative procedure is applied, by comparing the values between adjacent indices.

For example, if the signs are different, or if the new value is 0, we can decide to split the intervals.

#include <iostream>
#include <vector>

int count_operations (const std::vector<int> &A) {
    int n = A.size();
    if (n == 0) return 0;
    int count = std::abs (A[0]);
    for (int i = 1; i < n;   i) {
        if (A[i]*A[i-1] > 0) {
            if(std::abs(A[i]) > std::abs(A[i-1])) {
                count  = std::abs(A[i]) - std::abs(A[i-1]);
            }
        } else {
            count  = std::abs(A[i]);
        }
    }
    return count;
}

int main() {
    std::vector<int> A = {1 , 1, -1};
    auto ans = count_operations (A);
    std::cout << ans << "\n";
    
    A = {3, -1, -1, 3};
    ans = count_operations (A);
    std::cout << ans << "\n";
    
    return 0;
}