leetcode121：买卖股票的最佳时机

题目链接

leetcode

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

C++ 代码

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

/*
    买入并且卖出一次
*/

/*
    贪心算法：实时更新最小值，当前价格减最小值来更新最大利润。
    
    时间复杂度：O(n)
        其中 n 为数组的长度。
        遍历一次数组，更新最大利润。
    空间复杂度：O(1)
*/
class Solution_0 {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }
        
        int maxProfit = 0, minPrice = INT_MAX;
        for (int i = 0; i < prices.size(); i++) {
            maxProfit = max(maxProfit, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }
        
        return maxProfit;
    }
};

/*
    状态转移方程：
        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]
    
    时间复杂度：O(n)
        其中 n 为天数，k 为交易数的上限。
        遍历一次数组，更新状态数组。
    空间复杂度：O(n)
        状态数组的大小为 nk。
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2));

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                // 初始化
                f[i][0] = 0;
                f[i][1] = -prices[i];
                continue;
            } else {
                // 状态计算
                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];
    }
};

/*
    思路同上，优化空间

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_2 {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 初始化
        int f_i0 = 0;       // 第 i 天结束后没有股票时的最大利润
        int f_i1 = INT_MIN; // 第 i 天结束后有股票时的最大利润

        // 状态计算
        for (int i = 0; i < n; i++) {
            f_i0 = max(f_i0, f_i1 + prices[i]); // 卖出股票
            f_i1 = max(f_i1, -prices[i]);       // 买入股票（只允许一次）
        }

        return f_i0; // 最终不能持有股票
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> prices_cases = {
        {7,1,5,3,6,4},
        {7,6,4,3,1}
    };

    for (auto& prices : prices_cases) {
        cout << "Input: prices = ";
        printArray(prices);
        cout << endl;

        int result = solution.maxProfit(prices);
        cout << "Output: " << result << endl;
    }

    return 0;
}