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.
这道题的核心是把“对任意连续子数组整体加 x”转化为对相邻差值的修复：为了让数组最终非递减，只需要从左到右观察当前元素相对前一个元素是否下降；如果 <code>power[i] < power[i-1]</code>，那么这一段必须额外补足差值 <code>power[i-1] – power[i]</code>，而这个补偿的最小总和正好就是所有下降量的累加。也就是说，答案可以直接通过一次线性扫描求出，时间复杂度 <code>O(n)</code>，只需要使用 <code>long</code> 累加，避免大数据下溢出。
