AWS provides scalable systems. A set of n servers are used for horizontally scaling an application.
The goal is to have the computational power of the servers in non-decreasing order. To do so, you can increase the computational power of each server in any contiguous segment by x.
Choose the values of x such that after the computational powers are in non-decreasing order, the sum of the x values is minimum.
Example
There are n = 5 servers and their computational power = [3, 4, 1, 6, 2].
Add 3 units to the subarray (2, 4) and 4 units to the subarray (4, 4). The final arrangement of the servers is [3, 4, 4, 9, 9]. The answer is 3 + 4 = 7.
Complete the makePowerNonDecreasing function below.
The function is expected to return a LONG_INTEGER.
The function accepts INTEGER_ARRAY power as parameter.
This problem can be solved with a simple greedy scan. Since you may increase any contiguous segment by some value x, the minimum total cost is exactly the sum of all downward drops between adjacent elements. Traverse the array from left to right, and whenever a server’s power is smaller than the previous one, add the difference to the answer. This gives an O(n) solution with O(1) extra space and should be accumulated in a long integer.
