题解 | 买卖股票的最好时机(一)

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

const int N = 1e5 + 1;
int n,dp[N][2],a[N];
//dp[i][0]表示当前没有股票,dp[i][1]表示当前有股票，最后的答案就是dp[n][0]

int main(){

    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];

    dp[1][1] = -a[1];
    dp[1][0] = 0;

    for(int i = 2;i<=n;i++){
        dp[i][0]  = max(dp[i-1][1]+a[i],dp[i-1][0]);
        dp[i][1] = max(dp[i-1][1],-a[i]);  
    }

    // for(int i = 1;i<=n;i++) cout<<dp[i][1]<<" ";cout<<"\n";
    // for(int i = 1;i<=n;i++) cout<<dp[i][0]<<" ";cout<<"\n";
    cout<<dp[n][0];

    return 0;
}

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344