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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int k;
    scanf("%d", &k);
    vector<int> ivec(k, -1);
    int j;
    for(int i = 0; i < k; ++i)
    {
        scanf("%d", &j);
        ivec[i] = j;
    }
    vector<vector<int>> price(k, vector<int>(2));   //设置动态规划数组，该动态规划数组代表当天持有或非持有股票时的最大利润，第一维代表天数，第二维为0代表非持有股票，为1代表持有股票
    price[0][0] = 0;
    price[0][1] = -ivec[0];
    for(int i = 1; i < k; ++i)
    {
        price[i][0] = max(price[i - 1][0], price[i - 1][1] + ivec[i]);  //当天非持有股票时的最大利润为上一日非持有股票或持有持票但今日卖出之间的最大值
        price[i][1] = max(price[i - 1][1], price[i - 1][0] - ivec[i]);  //当天持有股票时的最大利润为上一日持有股票或非票但今日买入之间的最大值 
    }
    printf("%d", price[k - 1][0]);
    return 0;
}
// 64 位输出请用 printf("%lld")