Maximum difference between two elements is equal to solve Maximum Subarray?

3
votes

In one book (Introduction to Algorithm, but I don't remember which chapter) I learned that to solve Maximum difference between two elements problem:

Maximum difference between two elements such that larger element appears after the smaller number.

Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9)

is equal to solve the maximum subarray problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

In order to solve Maximum difference between two elements problem for [2,3,10,6,4,8,1], it can be convert to a max subarray problem for array:

[1,7,-4,-2,4,-7] where 1 is difference between 2,3; 7 is difference between 3,10; etc.

I am wondering why.

1
arraysalgorithm

1 Answers

1
votes

Lets assume that the maximum difference in array A is between elements A[i] and A[j] and is equal to diff. 

diff = A[j] - A[i]           (j > i)

Lets also assume that between A[i] and [j] there are N elements.
You can also get the value diff by:

diff = (A[j]-A[j-1]) + (A[j-1]-A[j-2]) + ... + (A[i+2]-A[i+1]) + (A[i+1]-A[i])

As you might already see, each (A[*]-A[*-1]) represents an element in the differences array. Meaning that the subarray with the largest sum is equal to the maximum difference between every two elements.

In general:
Lets define B to be the difference array of A.
For each two elements A[i], A[j] when j>i:

A[j]-A[i]  =  B[i] + ... + B[j-1]  =  sum(B[k]) 
                                      for k=i to j-1