感觉比股票买卖4简单

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,k,a[N];
int dp[N][2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0]=0;
    dp[1][0]=dp[0][0];
    dp[1][1]=dp[0][0]-a[1];
    for(int i=2;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
        dp[i][1]=max(dp[i-1][1],dp[i-2][0]-a[i]);
    }
    printf("%d",dp[n][0]);
    return 0;
}