两元素间的最大差等于解最大子阵？

Question

在一本书（算法导论，但我不记得是哪一章）中，我学到了求解两元素间最大差值问题：

两个元素之间的最大差，使得较大的元素出现在较小的数之后。

查找数组（至少包含一个数字）中和最大的相邻子数组。

例如，给定数组[-2,1,-3,4,-1,2,1,-5,4]，相邻子数组[4,-1,2,1]的最大和=6。

为了解决[2,3,10,6,4,8,1]的两元素间最大差异问题，可以将其转化为数组的最大子数组问题：

我在想为什么。

Answer 1

假设数组A中的最大差异在元素A[i]和A[j]之间，并且等于diff。

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

我们还假设在a[i]和[j]之间有n元素。
还可以通过以下方法获得diff值：

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

您可能已经看到，每个(A[*]-A[*-1])表示差异数组中的一个元素。意味着具有最大和的子数组等于每两个元素之间的最大差值。

通常:
让我们将b定义为a的差异数组。
对于每两个元素a[i]，j>i:

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