[Acwing] 3393. 最大序列和 线性DP

传送门 : https://www.acwing.com/problem/content/description/3396/
刚刚debug一波,没想到在这题又被坑了

这是Ac代码,但是这个样例输出就是不符

让我一直改 QAQ ,一交就过了

看完题目大概都知道了

我们就一维状态表示:
当前位置的最大值

状态计算

• 本身(要么本身最大) f[i] = f[i]
• 要么可以通过前面的转移 (因为是连续的所以不会O n^2 直接O n的做就行) f[i]=f[i-1]+f[i]

#include 
using namespace std;
using ll = long long;
const int N = 1e6+10;
const int _INF =-(1<<31);
int n;

ll f[N];
ll ans = _INF;

void solve()
{
    cin>>n;

    f[0] = _INF;
    for(int i=1;i<=n;i++)
    {   
        cin>>f[i];
        f[i] =max(f[i-1]+f[i],f[i]);
    }
    
    for(int i=1;i<=n;i++)
    ans = max(f[i],ans);
    cout<