数组中的连续最大和 - 动态规划

Question

我正在学习有关动态 programming.and 的教程 link ： http://www.8bitavenue.com/2011/11/dynamic-programming-maximum-contiguous-sub-sequence-sum/ 他们得出了一个关系：

M[j] = Max (A[j], A[j] + M[j-1])

但是在实现这个的实际代码中我无法理解他们是如何使用它的。这是他们的实现

//Initialize the first value in (M) and (b)  
M[1] = A[1];  
b[1] = 1;  

//Initialize max as the first element in (M)  
//we will keep updating max until we get the  
//largest element in (M) which is indeed our  
//MCSS value. (k) saves the (j) position of   
//the max value (MCSS)  
int max = M[1];  
int k = 1;  

//For each sub sequence ending at position (j)  
for (int j = 2; j <= n; j++)  
{  
    //M[j-1] + A[j] > A[j] is equivalent to M[j-1] > 0  
    if (M[j-1] > 0)  
    {  
        //Extending the current window at (j-1)  
        M[j] = M[j-1] + A[j];  
        b[j] = b[j-1];  
    }  
    else  
    {  
        //Starting a new window at (j)  
        M[j] = A[j];  
        b[j] = j;  
    }  

    //Update max and save (j)  
    if (M[j] > max)   
    {  
        max = M[j];  
        k = j;  
    }  
}  

print ("MCSS value = ", max,  " starts at ", b[k],  " ends at ", k);

我的问题是这个程序中如何使用导出的公式??

他们不应该将 a 用于这样的事情吗：

for i in A:
  M[j] = Max (A[j], A[j] + M[j-1])

Answer 1

您的问题的答案已在此行中给出：

//M[j-1] + A[j] > A[j] is equivalent to M[j-1] > 0

if语句选择A[j]和M[j-1]+A[j]中较大的值。这样你会更清楚吗？

if (M[j-1] + A[j] > A[j]) // is exact the same thing as M[j-1] > 0, but less elegant
{   
     M[j] = M[j-1] + A[j];
     b[j] = b[j-1];
}
else
{
    M[j] = A[j];
    b[j] = j;
}

数组中的连续最大和 - 动态规划

continous max sum in array -Dynamic programming

c++

arrays

logic

dynamic-programming