As you know, there is an algorithm for finding the maximum possible increment in an array of size n in O(n).

For example, given [11, 9, 7, 12, 8, 20, 16], the maximum increment is a[5] - a[2] == 20 - 7 == 13.

A variation of this algorithm is to find the sum of all such increments. For example, given [1, 10, 2, 9, 3, 7], the result is (10 - 1) + (9 - 2) + (7 - 3). Or given [1, 10, 1, 10, 1, 10], the result is (10 - 1) + (10 - 1) + (10 - 1).

It is easy to find an O(n²) algorithm for this varation:

• Find the maximum increment and in the input and return it the tuple (last-index, value)
• Add value to maximum increment of the subset of array starting from last-index + 1
• Continue until the array size is 0 or 1

For [1, 10, 2, 9, 3, 7], the steps will be like this:

findMaximumIncrementOf([1, 10, 2, 9, 3, 7]) = (1, 9), add 9 to temp
findMaximumIncrementOf([2, 9, 3, 7]) =  (1, 7), add 7 to temp, making it 16
findMaximumIncrementOf([3, 7]) = (1, 4), add 4 to temp, making it 20

It is easy to see that the worse case complexity of this algorithm is O(n²). Are there any more time efficient algorithms available?