首页 > 代码库 > 每日一九度之 题目1077:最大序列和

每日一九度之 题目1077:最大序列和

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:6264

解决:1870

题目描述:

给出一个整数序列S,其中有N个数,定义其中一个非空连续子序列T中所有数的和为T的“序列和”。
对于S的所有非空连续子序列T,求最大的序列和。
变量条件:N为正整数,N≤1000000,结果序列和在范围(-2^63,2^63-1)以内。
 

输入:

第一行为一个正整数N,第二行为N个整数,表示序列中的数。

输出:

输入可能包括多组数据,对于每一组输入数据,
仅输出一个数,表示最大序列和。

样例输入:
51 5 -3 2 461 -2 3 4 -10 64-3 -1 -2 -5
样例输出:
97-1

动态规划题。多练习。

关于LLONG_MIN

这个是个宏定义,在 limits.h 头文件下。

//Asimple#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <vector>#include <cctype>#include <cstdlib>#include <stack>#include <cmath>#include <set>#include <map>#include <string>#include <queue>#include <limits.h>#define INF 0x7fffffffusing namespace std;const int maxn = 105;typedef long long ll;int n;ll num;int main(){    while( ~scanf("%d",&n) ){        ll Max = LLONG_MIN;        ll temp = 0;         for(int i=0; i<n; i++){             scanf("%lld",&num);             if( temp > 0 ){                 temp += num ;             } else temp = num;             if( temp > Max ) Max = temp;         }         printf("%lld\n",Max);    }     return 0;}

 

每日一九度之 题目1077:最大序列和