首页 > 代码库 > 九度OJ 1077 最大子序列和 （动态规划）
九度OJ 1077 最大子序列和 （动态规划）
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：4836
解决：1401
- 题目描述：
给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。
对于S的所有非空连续子序列T，求最大的序列和。
变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。
- 输入：
第一行为一个正整数N，第二行为N个整数，表示序列中的数。
- 输出：
输入可能包括多组数据，对于每一组输入数据，
仅输出一个数，表示最大序列和。
- 样例输入：
5 1 5 -3 2 4 6 1 -2 3 4 -10 6 4 -3 -1 -2 -5
- 样例输出：
9 7 -1
#include<stdio.h>
#include<string.h>
#include<math.h>
long long int MS;
int N;
long long int a[1000010];
long long int b[1000010];
int i;
int j;
int k;
void so(){
b[0]=a[0];
for (int i = 1; i < N; i++)
{
if(b[i-1]+a[i]>a[i])
b[i]=b[i-1]+a[i];
else
b[i]=a[i];
if(b[i]>MS)
MS=b[i];
}
}
int main(int argc, char *argv[])
{
// freopen("1077.in", "r", stdin);
while(~scanf("%d",&N)){
memset(a,0,sizeof(a));
for(i=0;i<N;++i)
scanf("%lld",&a[i]);
MS=a[0];
so();
printf("%lld\n",MS);
}
return 0;
}
/**************************************************************
Problem: 1077
User: kirchhoff
Language: C
Result: Accepted
Time:250 ms
Memory:16540 kb
****************************************************************/设b[j]表示第j处，以a[j]结尾的子序列的最大和。
注意：b[j]并不是前j-1个数中最大的连续子序列之和，而只是包含a[j]的最大连续子序列的和。我们求出b[j]中的最大值，即为所求的最大连续子序列的和。
递推公式：b[j]=max{a[j],b[j-1]+a[j]}九度OJ 1077 最大子序列和 （动态规划）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。