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

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

int main() {
    int n;
    cin >> n;
    vector<int> prices;
    int tmp = 0;
    for(int i = 0; i < n; i++){
        cin >> tmp;
        prices.push_back(tmp);
    }
    //分析
    //1.前一天持有股票：
    //1.1 继续持有，不需要操作
    //1.2 抛售股票 dp[i - 1][1] -> dp[i][0]
    //2.前一天没有股票
    //2.1 继续不持，不需要操作
    //2.2 持有股票 dp[i - 1][0] -> dp[i][1]
    int dp[n ][2]; //dp[i][0]表示不持有股票， dp[i][1]表示持有股票
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for(int i = 1; i < n; i++){
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = max(dp[i - 1][1], -prices[i]);
    }
    cout << dp[n - 1][0] << endl;
    return 0;


}