P1115题解

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])$$

代码如下：

#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;
}