状态机

$ 时间复杂度O(N)，空间O(3N) $
每一个状态只用到了上一层的状态，所以可以优化成常数空间

参考文献

算法提高课

AC代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, INF = -0x3f3f3f3f;

int f[N][3];
int n, w;

int main(){
    cin >> n;
    //初始化
    memset(f, -0x3f, sizeof f);
    f[0][1] = 0;

    //状态机
    for (int i = 1 ; i <= n ; i ++){
        cin >> w;
        f[i][0] = f[i - 1][2] + w;
        f[i][1] = max(f[i - 1][0], f[i - 1][1]);
        f[i][2] = max(f[i - 1][1] - w, f[i - 1][2]);
    }

    //输出答案
    int res = max(0, max(f[n][0], f[n][1]));
    cout << res;

    return 0;
}