P1115题解

P1115

题目描述

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

输入格式

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

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

输出格式

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

解题思路

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

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

转移方程式如下：

代码如下：

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