P1115

题目描述

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

输入格式

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

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

输出格式

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

解题思路

当然你可以暴力枚举$O(n^3)$
所以还是动规吧·······$O(n)$

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

转移方程式如下:

$$dp[i]=max(dp[i-1]+a[i],dp[i])$$

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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;
}

评论