P1115题解

P1115

题目描述

给出一段序列,选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个正整数,表示了序列的长度。

第二行包含个绝对值不大于的整数,描述了这段序列。

输出格式

一个整数,为最大的子段和是多少。子段的最小长度为

解题思路

当然你可以暴力枚举
所以还是动规吧·······

设数组存放的一第个数字为结尾的连续字串和最大的值

转移方程式如下:

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>


using namespace std;

int main()
{
int n,a[200005],tmp;
cin>>n;
cin>>tmp;
a[1]=tmp;
for (int i=2;i<=n;i++)
{
cin>>tmp;
a[i]=max(tmp,a[i-1]+tmp);
}
int m=-999999999;
for (int i=1;i<=n;i++)
if (a[i]>m) m=a[i];
cout<<m;
return 0;
}
-------------本文结束,感谢您的阅读-------------