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 (x > 0). Choose the values of x such that after all operations, the computational powers are in non-decreasing order, and the sum of the x values is minimum.
Given the initial array power[n] representing the computational powers of the servers, determine the minimum sum of x values needed to make the array non-decreasing.
5 3 4 1 6 2
7
Initial array: [3, 4, 1, 6, 2].
- Add 3 units to subarray (2, 4): [3, 4, 4, 9, 5].
- Add 4 units to subarray (4, 4): [3, 4, 4, 9, 9].
Array is now in non-decreasing order. Sum of x = 3 + 4 = 7.
3 3 2 1
2
Initial array: [3, 2, 1].
- Drop from index 0 to 1 is 3 - 2 = 1.
- Drop from index 1 to 2 is 2 - 1 = 1.
Total minimum sum of x = 1 + 1 = 2.
1. Let difference array D[i] = power[i] - power[i-1] for i = 1..n-1. The array is non-decreasing iff D[i] >= 0 for all i. 2. When adding x to subarray [L, R], D[L] increases by x and D[R+1] decreases by x. To avoid penalizing later elements, optimal operations always extend to the end (R = n-1, suffix operations). 3. Any decrease where power[i] < power[i-1] represents an unavoidable deficit of (power[i-1] - power[i]) that must be compensated by adding at least that amount to a suffix starting at index i. 4. Therefore, minimum total sum of x is simply the sum of all downward drops: ans = sum(max(0, power[i-1] - power[i])) for all i from 1 to n-1. 5. Operates in O(N) time and O(1) space.