滚动数组优化

#include<bits/stdc++.h>
using namespace std;

int f[5],g[5];

int main(){
    int n;
    cin>>n;
    f[0]=f[1]=INT_MIN,f[2]=0;
    for(int i=1;i<=n;++i){
        int w;
        cin>>w;

        memcpy(g,f,sizeof(g));
        f[0]=max(g[0],g[2]-w);
        f[1]=g[0]+w;
        f[2]=max(g[1],g[2]);
    }
    cout<<max(f[1],f[2]);

    return 0;
}

空间复杂度为 $\Theta(1)$.