买卖股票的最佳时机 II：获取最大利润的策略

买卖股票的最佳时机 II

问题描述

给定一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回你能获得的最大利润。

示例

示例 1:

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出，这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7。

示例 2:

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出，这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4。

示例 3:

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下，交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示

• 1 <= prices.length <= 3 * 10^4
• 0 <= prices[i] <= 10^4

解题思路

1. 问题分析

与“买卖股票的最佳时机 I”不同，此问题允许多次买卖来获取利润。关键在于捕捉每一个可能的利润机会，即只要后一天的价格比前一天高，就可以进行一次买卖。

2. 贪心算法

利用贪心算法，我们只关心从任何一天到下一天的价格差，如果这个价格差是正的，我们就将其加到总利润中。这样可以确保捕捉到所有的上升波段。

3. 代码实现

Java

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
}

Python

def maxProfit(prices):
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]
    return max_profit

4. 复杂度分析

• 时间复杂度: O(n)，只需一次遍历。
• 空间复杂度: O(1)，无需额外空间。

总结

“买卖股票的最佳时机 II”通过贪心算法简单高效地解决了股票交易问题，使得每次只要有利润就进行交易，从而最大化总利润。这个策略是解决此类问题的常用方法。