Interview-Min-Total-Increment-for-NonDecreasing-Array

Problem Overview

Problem Description

You are given an array power representing the computational strength of $n$ servers. The objective is to make the array non-decreasing (where each element is greater than or equal to the previous one. i.e. $power[i] \ge power[i-1]$) with the minimum total cost.

You can choose any contiguous segment (a subarray) of servers and increase the power of every server in that segment by a value x. Find the minimum possible sum of all x values used to achieve the non-decreasing state.

Example:

Input: $power = [3,4,1,6,2]$

• Compare 4 and 3: $4 \ge 3$, no action needed.
• Compare 1 and 4: $1 < 4$. The difference is $3$.
  Lift the suffix by $3$. Total $x = 3$.
• Compare 6 (now $9$) and 4: $9 \ge 4$, no action needed.
• Compare 2 (now $5$) and 9: $5 < 9$. The difference is $4$.
  Lift the suffix by $4$. Total $x = 3 + 4 = 7$.

Output: 7

🧠 Summary of Thoughts

We don’t actually need to update the values because of Relative Difference Stability: When we lift a whole segment by x, every element in that segment moves up together.The gap between any two neighbors inside that segment remains exactly the same.Therefore, the “dips” that existed in the original array’s tail will still be the same size in the “updated” array. We just need to sum those original dip sizes.

Formula:

The minimum sum is simply the total of every “downward drop” in the original array:
$$S = \sum_{i=1}^{n-1} \max(0, power[i-1] - power[i])$$

✅ Code（Java）

import java.util.*;

class Result {
    public static long findMinimumSum(List<Integer> power) {
        if (power == null || power.size() <= 1) {
            return 0;
        }
        long minSum = 0;
        for (int i = 1; i < power.size(); i++) {
            // If the trend shows decreasing, then add the difference between them
            if (power.get(i) < power.get(i - 1)) {
                long diff = (long) power.get(i - 1) - power.get(i);
                minSum += diff;
            }
        }

        return minSum;
    }
}