122. 买卖股票的最佳时机 II

一、题目描述

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

二、解题思路

想要获取最大收益，最好的情况就是在谷值买入，峰值卖出。

但是如果谷值和峰值都很多的情况下，这个时候该什么时候买入卖出呢？

• 最优的情况是在相邻的谷值和峰值买入卖出，收益才能最大。

验证过程：

比如谷值是 a，峰值 b（b > a，否则收益为负数），此时收益就是：

b - a

假设 a，b之间还存在另外的峰值 c, 谷值 d，其中有 d < c。

那么相邻谷值峰值买入卖出的收益是：

c - a + b - d = b - a + c - d > b - a

也就是说，如果在一对谷值峰值之间，还存在别的谷值峰值，那它们取得的收益就不是最大值。

因此，相邻谷值峰值买入卖出的情况下能够获取最大收益。

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

/**
 * 最大收益
 *
 * @param prices 价格数组
 * @return 最大收益
 */
private int maxProfit(int[] prices) {
    int sumVal = 0, n = prices.length;
    for (int rp = 1; rp < n; rp++) {
        if (prices[rp] > prices[rp - 1]) {
            // 谷值到峰值之间的上升值
            sumVal += prices[rp] - prices[rp - 1];
        }
    }
    return sumVal;
}