最大子段和

佚名 6年前 (2019-04-21) 随笔 2099人围观抢沙发百度已收录

题目描述

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

输入

每组输入包括两行，第一行为序列长度n，第二行为序列。

输出

输出字段和的最大值。

样例输入 Copy

5
-1 0 1 2 3

样例输出 Copy

6

例1：
数组 m[]: -1 0 1 2 3
数组 c[]: -1 0 1 3 6

例2：

数组 m[]: 4 3 -8 7 8
数组 c[]: 4 7 -1 7 15

#include<bits/stdc++.h>
using namespace std;
 int c[100]; //该数组存放子段和
 int n;
 int fun(int m[100])
 {
     c[0]=m[0];
     int max=0;
     for(int i=1;i<n;i++)
     {
         if(c[i-1]>0)
         {
             c[i]=c[i-1]+m[i];
         }
         else
         {
             c[i]=m[i];
         }
         if(c[i]>max) //找出最大子段和
             {
                 max=c[i];
             }
     }
     return max;

 }
int main()
{
    int m[100];
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
        {
            cin>>m[i];
        }
        fun(m);
        cout<<fun(m)<<endl;
    }
       return 0;
}