[Leetcode]122. Best Time to Buy and Sell Stock II

约定不等于承诺〃 2022-06-13 23:59 108阅读 0赞

# 122. Best Time to Buy and Sell Stock II #

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like(ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time(ie, you must sell the stock before you buy again).

**给定一个数组，表示股票第i天的价格，怎么进行股票买卖才能获得最大的利润。可进行多次股票买卖**

**解题思路**  
本题可以将数组中的所有增区间找出来，取增区间的首尾两个节点作为股票买入和卖出的时间点，以这两个时间点作为买卖时间则一定能够获得利润，然后再将所有的利润加起来便可以得到最大的利润。  
本题的关键在于找出所有的增区间，因为股票买卖只有在增区间才能获得利润，在减区间是无法获得利润的。

代码实现如下：

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.size() == 0)
                return 0;
            int profit = 0;
            int i = 0;
            int len = prices.size()-1;
            while(i <= len)
            {
                int buy = 0,sell = 0;
                while(i <= len && prices[i] > prices[i+1])
                    i++;    //递减区间
                buy = i++;  //在减区间中最小的值（谷底值，和增区间交叉的值）买入
    
                while(i <= len && prices[i] > prices[i-1])
                    i++;    //递增区间
                sell = i-1; //在增区间中最大的值（谷峰值，和减区间交叉的值）卖出
    
                profit += prices[sell] - prices[buy];
            }
            return profit;
        }
    };

本题跟\[Leetcode 121\]题最大的不同在于，本题并不限制股票交易的次数，而\[Leetcode 121\]则是严格限制了股票交易次数只能是一次。  
本题相对也是比较简单，而在\[Leetcode 123\]与本题相似，但\[Leetcode 123\]严格限制了股票买卖次数只能是2次。\[Leetcode 123\]相对难度有所提高，下一篇将主要讲解\[Leetcode 123\]的解题思路。