Problem Brief

Make Power Non-decreasing

NEW GRADINTERNOA

See Amazon online assessment and hiring insights

Suppose we, together, run a cloud computing company that offers a highly scalable system that allows applications to expand efficiently. We now have a set of n servers that are used to horizontally scale an application.

The objective is to ensure that the computational power of these servers is arranged in a non-decreasing order.

To achieve this, we are allowed to increment the computational power of any contiguous segment of servers by a chosen value z. The challenge is to determine the optimal values of z for different segments so that, once the computational powers are in the desired non-decreasing order, the total sum of all chosen z values across the entire process is minimized.

1Example 1

Input

powa = [3, 4, 1, 6, 2]

Output

Explanation

Add three units to the subarray [2, 4] and four units to the subarray [4, 4,]. The final arrangement of the server is: [3, 4, 4, 9, 9]. The ans is 3 + 4 = 7. (As shown in the image)

2Example 2

Input

powa = [3, 2, 1]

Output

Explanation

Adding one unit to subarray (1, 2) and one unit to subarray (2, 2). The final arrangement of server is [3, 3, 3].

3Example 3

Input

powa = [3, 5, 2, 3]

Output

Explanation

Lets add three units to subarray (2, 3). The final arrangement of servers is now 3, 3, 5, 6...(To be continued...) This test case was added on 2025-02-15.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 10^5

1 <= powa[i] <= 10^9

Draft autosaves locally

public int makePowerNonDescreasing(int[] powa) {
  // write your code here
}

Input

powa

[3, 4, 1, 6, 2]

Output