剑指63：股票的最大利润

传送门

nowcoder
leetcode

题目描述

把某股票的价格按照时间先后顺序存储在数组中，
请问买卖该股票一次可能获得的最大利润是多少？

C++ 代码 - nowcoder

/*
    贪心策略
    假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;

        int minNum = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.size(); i ++) {
            minNum = min(minNum, prices[i]);
            maxProfit = max(maxProfit, prices[i] - minNum);
        }
        
        return maxProfit;
    }
};

C++ 代码 - leetcode

/*
    贪心策略
    假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。
*/
class Solution {
public:
    int bestTiming(vector<int>& prices) {
        if (prices.empty()) return 0;

        int minNum = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.size(); i ++) {
            minNum = min(minNum, prices[i]);
            maxProfit = max(maxProfit, prices[i] - minNum);
        }
        
        return maxProfit;
    }
};

/*
	动态规划
	
	状态定义：
		dp[i][k][0 or 1]
		0 <= i <= n - 1, 1 <= k <= K
		n 为天数，K 为交易数的上限，0 和 1 代表是否持有股票。
	状态转移：
		dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]) 
		// max(今天 rest, 今天 sell)
		dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]) 
		// max(今天 rest, 今天 buy)
	base case：
        dp[-1][...][0] = dp[...][0][0] = 0
        dp[-1][...][1] = dp[...][0][1] = -infinity
        
	特化到 k = 1 的情况
	状态转移：
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = max(dp[i - 1][1], -prices[i])
	base case：
        dp[i][0] = 0;
        dp[i][1] = -prices[i]
*/
class Solution {
public:
    int bestTiming(vector<int>& prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2));

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                // base case
                f[i][0] = 0;
                f[i][1] = -prices[i];
                continue;
            }
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]);
            f[i][1] = max(f[i - 1][1], -prices[i]);
        }
        
        return f[n - 1][0];
    }
};