[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]

CODE

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

    f[0] = _INF;
    for(int i=1;i>f[i];
        f[i] =max(f[i-1]+f[i],f[i]);
    }
    
    for(int i=1;i