algorithm - 动态规划(最大总和)

Question

给定一个 n 个实数序列 A(1) ... A(n)，确定一个连续的子序列 A(i) .. . A(j) 其子序列中元素之和最大。

解决方法是:

M(j) = max sum over all windows ending in j

M(j) = max{M(j-1) +A[j], A[j]}

有人可以解释一下这对于以下子序列是如何工作的吗:1、5、-10、5。因为在第一个 5 和 -10 之间，递归选择了 -4 (M(j-1) +A[j]) 或 -10 (M(j-1) +A[j])。但是，最好的总和是 6。

那么重现不应该是:

M(j) = max{M(j-1) +A[j], A[j], M(j-1)}

Answer 1

如您所说，M[j] = 所有以 j 结尾的窗口的最大总和。所以在为 0 和 n - 1 之间的所有 j 计算完 M[j] 之后。您输出其中的最大值。这是 C++ 中的示例代码。

int findMax(int a[], int n){
    int * M = new int[n];
    M[0] = a[0];
    for(int i=1; i<n; i++)
        M[i] = max(M[i-1] + a[i], a[i]);
    int ans = M[0];
    for(int i=1; i<n; i++)
        ans = max(ans, M[i]);

    return ans;
}

对于您的序列 {1, 5, -10, 5}。 M = {1, 6, -4, 5} 答案是 M 中的最大值，即 6。