Codility 最大利润问题：为什么累积差和解相当于 2 指数差解？

Question

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367
If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367
the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..400,000];
each element of array A is an integer within the range [0..200,000].

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

这是我在 youtube 上找到的解决方案

function solution(arr) {
    let max = 0;
    let acc = 0;

    for(let i=1; i<arr.length; ++i) {
        const diff = arr[i] - arr[i-1];
        acc = acc + diff;
        if(acc > 0) {
            if(acc > max) {
                max = acc;
            }
        } else {
            acc = 0;
        }
    }

    return max;
}

我的问题如下：

在上面的测试用例中，我们知道在一笔交易中 array[5] - array[one] = 356（我们在第 5 天买入并在第 1 天卖出以获得最大利润）。我们不考虑介于两者之间的任何事情，这就是问题所在

使用累积的差值和并将它们相加（因此其他数字会介入并干扰计算）

为什么累加差值和等于 array[5] - array[one] = 356？

Answer 1

考虑只有三个元素的情况。很明显，

arr[i + 2] - arr[i + 1] + arr[i + 1] - arr[i] = arr[i + 2] - arr[i]

作为术语

arr[i + 1]

被抵消了。

更一般地，当 i 的范围从

start

到

end - 1

时，arr[i + 1] - arr[i] 之和是等于 arr[end] - arr[start] 的

伸缩总和

。您可以通过求和性质或归纳来证明这一点。

基于此，将价格数组转换为差值数组后，答案就是最大子数组和，可以通过Kadane算法找到。