【基础练习】【线性DP】codevs2622 数字序列（最大连续子序列和）题解

曾经终败给现在 2022-08-02 06:04 163阅读 0赞

版权信息

这道题目本质就是朴素的最大连续子序列和

直接上题目和代码

题目描述 Description

给定一个长度为n的一个序列A1，A2，…，An，求序列中连续子序列的最大和。

例如：当输入为-5，3，5，7，-15，6，9，27，-36，10时，连续子序列6，9，27的和为42是最大值；而当序列变成-5，3，5，8，-15，6，9，27，-36，10时，连续子序列3，5，8，-15，6，9，27的和为43是最大值。

输入描述 Input Description

第一行为n (n≤1000)，第二行为n个数，表示序列Ai（-10000≤Ai≤10000）。

输出描述 Output Description

一个数，表示连续子序列的最大和。

样例输入 Sample Input

\-5 3 5 8 -15 6 9 27 -36 10

样例输出 Sample Output

数据范围及提示 Data Size & Hint

--------------------

\-10000≤Ai≤10000

n≤1000

思路很简单，如果这个数本身比加上前面序列的值就采用本身，否则就采用加上前面序列的值

代码菌~

//codevs2622 数字序列（最大连续子序列和） 线性DP
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=1000+10;
    int a[maxn],f[maxn];
    int n;
    
    int main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        f[1]=a[1];
        for (int i=2;i<=n;i++)
        {
            f[i]=max(a[i],f[i-1]+a[i]);
        }
        int ans=0;
        for (int i=1;i<=n;i++) ans = max(ans , f[i]);
        printf("%d\n",ans);
        return 0;
    }

——疏影斜横水清浅，暗香浮动月黄昏

[ametake]: http://blog.csdn.net/ametake