博客

7-2 最大子段和 (40分)

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

输入格式:

输入有两行：

第一行是n值（1<=n<=10000)；

第二行是n个整数。

输出格式:

输出最大子段和。

输入样例:

在这里给出一组输入。例如：

6
-2 11 -4 13 -5 -2

输出样例:

在这里给出相应的输出。例如：

20

代码实现：

#include <iostream>
#include <stdlib.h>
#include <memory.h>
#define MAXN 10000
using namespace std;
int main()
{
    int n;
    int z=0;
    int a[MAXN];
    int s[10000][10000];
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    
    for (int i=1; i<=n; i++)
    {
        if(a[i]<0) z++;
    }
    
    if(z==n) {cout<<0;return 0;}  //所有负数则输出0
    else{
    
            for (int i=1; i<=n; i++) s[i][i] = a[i];    //初始化

            for (int r=2; r<=n; r++)
            {
                for(int i=1 ; i<=n-r+1 ;i++)
                {
                    s[i][i+r-1]=a[i];   //初始化
                    for(int j=i+1; j<=i+r-1 ;j++)    //i+r-1最后一个矩阵编号
                        s[i][i+r-1]+=a[j];      //持续加
                }
            }
            
            int t=s[1][1];
            for (int i=1; i<=n; i++)
            {
                for (int j=i; j<=n; j++)
                {
                    if(t<s[i][j]) t=s[i][j];    //寻找最大的s
                }
            }
            cout<<t;
        }
}