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

1、解题思路

1. 贪心算法：每次在价格上升时买入和卖出，累计所有上升区间的利润总和。这样可以将多次买卖的总利润最大化。一次遍历即可完成，时间复杂度 O(n)，空间复杂度 O(1)。
2. 动态规划：定义 dp[i][0] 表示第 i 天不持有股票时的最大利润。定义 dp[i][1] 表示第 i 天持有股票时的最大利润。状态转移方程： dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])最终答案为 dp[n-1][0]。
3. 空间优化：由于 dp[i] 仅依赖于 dp[i-1]，可以只用两个变量来存储状态，优化空间复杂度为 O(1)。

2、代码实现

C++（贪心算法）

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int profit = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
};

C++（动态规划 + 空间优化）

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if (prices.empty()) {
            return 0;
        }

        int hold = -prices[0], cash = 0;
        for (int i = 1; i < prices.size(); ++i) {
            cash = max(cash, hold + prices[i]);
            hold = max(hold, cash - prices[i]);
        }

        return cash;
    }
};

Java（贪心算法）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
}

Java（动态规划 + 空间优化）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if (prices.length == 0) return 0;
        int hold = -prices[0], cash = 0;
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(cash, hold + prices[i]);
            hold = Math.max(hold, cash - prices[i]);
        }
        return cash;
    }
}

Python（贪心算法）

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit += prices[i] - prices[i-1]
        return profit

Python（动态规划 + 空间优化）

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        if not prices:
            return 0
        hold, cash = -prices[0], 0
        for i in range(1, len(prices)):
            cash = max(cash, hold + prices[i])
            hold = max(hold, cash - prices[i])
        return cash

3、复杂度分析

• 时间复杂度 O(n)
• 空间复杂度 O(1)