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

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

int main() {          //本题为基本的股票买卖问题，采用动态规划方法可以解决
    int n;
    scanf("%d", &n);
    int j;
    vector<int> ivec(n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &j);
        ivec[i] = j;
    }
    vector<vector<int>> price(n, vector<int>(2));     //二维数字dp，price[i][0]代表第i天不持有股票，利润最大值，prince[i][1]代表当天持有股票利润最大值
    price[0][0] = 0;
    price[0][1] = -ivec[0];
    for(int i = 1; i < n; ++i)
    {
        price[i][0] = max(price[i - 1][0], price[i - 1][1] + ivec[i]);
        price[i][1] = max(price[i - 1][1], -ivec[i]);   //因为只能买卖一次股票。因此第i天买入可记为-ivec[i]
    }
    printf("%d", price[n - 1][0]);
    return 0;
}
// 64 位输出请用 printf("%lld")