最大连续子数组总和的输出显示不正确

Question

我正在关注一个网站的教程（下面的链接），并从那里我试图实现“最大连续和子数组”的标准问题。但他们在尝试使用样本数组代码之后：{15，-1，-3,4，-5}显示的答案为：“SMCSS值= 4从3开始并在3结束”但它应显示最大值为15等开始和结束值为1.这里是代码： 最新错了吗和我该怎么修改？链接：以前http://www.8bitavenue.com/2011/11/dynamic-programming-maximum-contiguous-sub-sequence-sum/

#include<iostream> 
    #include<stdio.h> 
    //Initialize the first value in (M) and (b) 
    using namespace std; 
    int main(){ 

    int M[8],b[8]; 

    int A[] = {15,-1,-3,4,-5}; 


    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; 
    int n = sizeof(A)/sizeof(int); 
    cout<<n; 
    //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; 
     } 
    } 

    cout<<"MCSS value = "<<max<<"starts at "<<b[k]<<"ends at"<<k; 
    return 0; 
} 

Answer 1

两件事情我会来挖入指数：

1. 数组编号在C++开始0。所以我假设这一切都开始于M[0] = A[0]; b[0] = 0;

2. 你应该考虑使用std::vector这是处理数组的方式std::vector。

Here是一个可行的解决方案。

Answer 2

这里正确的代码

#include<iostream> 
#include<stdio.h> 
//Initialize the first value in (M) and (b) 
using namespace std; 
int main() 
{ 

    int M[8],b[8]; 

    int A[] = {15,-1,-3,4,-5}; 

    M[0] = A[0]; 
    b[0] = 0; 

    //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[0]; 
    int k = 0; 
    int n = sizeof(A)/sizeof(int); 
    cout<<n<<endl; 
    //For each sub sequence ending at position (j) 
    for (int j = 1; 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; 
     } 
    } 

    cout<<"MCSS value = "<<max<<" starts at "<<b[k]<<" ends at"<<k; 
    return 0; 
} 

你应该从0开始的索引;