视频题解
时间轴
大盗阿福 0:00
股票买卖 IV 2:15
股票买卖 V 4:55
设计密码 7:25
AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){
int n; cin >> n;
vector<int> a(n + 1); for(int i = 1; i <= n; i ++) cin >> a[i];
vector<vector<int>> dp(n + 1, vector<int>(3, -2e18));
dp[0][0] = 0;
for(int i = 1; i <= n; i ++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][2] + a[i];
dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] - a[i]);
}
cout << max(dp[n][0],dp[n][1]) << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
while(T --){
solve();
}
}