Amazon Interview SDE1

Round 1

Questions: Given an array of positive integers including 0. At each operation, you can choose a non-empty subarray and decrement all elements in it by 1. Find the minimum number of operations required to make all elements of the array equal to 0.

For example:

arr = [3,1,4,2]

• subarray[0:3] -> [2,0,3,1]
• subarray[2:3] -> [2,0,2,0]
• subarray[0:0] (2 times) -> [0,0,2,0]
• subarray[2:2] (2 times) -> [0,0,0,0]

Total => 1 + 1 + 2 + 2 = 6

So, ans = 6

Constraint: Size of the array can be 1e5.

Expected to do it in O(NlogN) or better.