学步园

RT，求一数组中元素的最大连续子段和。

方法一。

  不考虑超时的影响，可以使用循环暴力解决，a[i][j]表示i是开头元素，j为结尾元素，需要使用三层循环，时间复杂度为0(n^3);

#include<iostream>
using namespace std;
int b[100][100];
int main()
{
    int a[100];
    int n,k;
    cin>>n;
    for(k=0;k<n;++k)
    cin>>a[k];
    int i,j;
    for(i=0;i<n;++i)
    for(j=i;j<n;++j)
    for(k=i;k<=j;++k)
    {
      b[i][j]=b[i][j]+a[k];
    }
    int max=-222;
    for(int s=0;s<n;++s)
    for(int B=0;B<n;++B)
    if(b[s][B]>max)
    max=b[s][B];
    cout<<max<<endl;
    system("pause");
    return 0;
} 
        
    

方法二。

  方法一中的a[i][j]，可以由Sum[j]-Sum[i-1]到，到使时间复杂度降为O(n^2)，代码略~

方法三。时间复杂度O(n).

  利用动态规划，由于我是看别人才理解此算法的，所以说说我的理解吧。

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
      int n,a[100001];
      memset(a,0,100001);
      cin>>n;
      for(int i=0;i<n;++i)
      cin>>a[i];
      int temp=0,max=-32222,k=1;
      for(int j=0;j<n;++j)
      {
      temp=temp+a[j];                    //子段之间的相加
      if(temp>max)
      {
      max=temp;                              //保存最大值的信息
      }
      if(temp<0)                         //舍弃之前的子段
      {
                temp=0;
      }
      }
      cout<<max<<endl;
    }
    system("pause");
    return 0;
}

举个例子，a[4]={-11,-8,9,2}; 显然最大子段和是 9+2=11；

该代码从头到尾扫描一次，如果只有一项，则最大子段和是它本身，不管是否为负数还是正数。

假设第二项为正数的话，显然最大子段和就是第二项本身了，该怎样解决了呢，这样想，因为这是求连续子段和，倘若该项的前n-1项连续子段和为负数，则最大子段和max就会改变，因为一个数加上一个负数，值会减小。所以当前n-1项连续子段和为负数时，就舍弃这一段，从头开始。但注意，最大连续子段和中的元素可以允许有负数的存在，此时就需要设置一个max来保存最大值的情况，如果增加，则更新max的情况，否则不更新。