AT_donuts_live2014_3

dengruixun · 2023-08-20 09:53:26 · 题解

实际上，这道题目和 P1115 没区别。

本题目可以用动态规划来做。

最暴力的方法就是枚举起点，枚举终点，循环求和，但是可能会 RE。

于是我们用动态规划来写：

状态：dp[i] 表示以第 i 个数结尾的最大子段和。

状态转移方程：dp[i] = \max(dp[i-1]+x,x)。

正确代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    const int N = 1e6 + 5;
    int x , dp[N] = {0} , maxi = -1e9 , n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin >> x;
        dp[i] = max(dp[i-1]+x,x);
        maxi = max(maxi,dp[i]);
    }
    cout<<maxi;
    return 0;
}