求最大子序列

试题描述

 

给定一个整数序列a1、a2…an，求这个序列中的一个连续子序列，使得这个序列中的数的和最大。

输入

第一行，一个整数n。
第二行，n个整数，a1、a2...an。

输出

一行，一个整数，表示你所求的最大的和。

输入示例

8
3 -6 -8 4 7 -5 5 2

输出示例

13

其他说明

N<=500000，序列中所有数的绝对值均不超过1000。

C代码：

#include <stdio.h>
 
 int main(int argc, char* argv[]) {
     int n;
     scanf("%d", &n);
     int a;
 
     int mmax = 0;
     int max = 0;
     int s = 0;
     for(int i = 0; i < n; ++i){
         scanf("%d", &a);
         s += a;
         if(s > max) max = s;
         if(max > mmax) mmax = max;
 
         if(s <= 0){
              s = 0;
              max = 0;
         }
     }
     printf("%d\n", mmax);
     return 0;
 }