leetcode Best Time to Buy and Sell Stock III

落日映苍穹つ 2022-08-08 13:39 12阅读 0赞

# 题目 #

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

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:  
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目链接：[https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/][https_leetcode.com_problems_best-time-to-buy-and-sell-stock-iii]

有一个数组里面存放着一支股票每天的价格。设计一个算法求最大收益。限制是你最多可以买卖两次。你在再次买入之前应该先卖出。

# 分析 #

Best Time to Buy and Sell Stock [http://blog.csdn.net/u010902721/article/details/45829153][http_blog.csdn.net_u010902721_article_details_45829153]  
这道题解决的是只进行一次买卖，求最大收益。所以本题可以采用这个思想。现将数组分成两部分，每部分进行一次买卖，求最大收益，然后求两个最大收益的和。进行划分的时候最笨的方法是i从0循环到len - 1。这样子时间复杂度就是O(n^2)。

优化：  
一次循环，i 从0到len - 1，用数组max\_profit\[i\]存储从0到i之间的最大收益，这样一次循环的时间复杂度是O(n)；再一次逆向循环， i从len - 1 到0，用数组max\_profit\_reverse\[i\]存储从i到len - 1之间的最大收益，这一次的时间复杂度也是O(n)。最后求最大收益和。总的时间复杂度是O(n)。

# 代码 #

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int len = prices.size();
            if(len <= 0)
                return 0;
            int max_profit[len] = {
       0};
            int buy_price = prices[0];
            int cur_profit = 0;
            for(int i = 0; i < len; i++){
                if(prices[i] < buy_price)
                    buy_price = prices[i];
                if(prices[i] - buy_price > cur_profit)
                    cur_profit = prices[i] - buy_price;
                max_profit[i] = cur_profit;//存放从0到i之间，进行一次买卖的最大收益
            }
            int max_profit_reverse[len] = {
       0};
            int high_price = prices[len-1];
            cur_profit = 0;
            for(int i = len-1; i >= 0 ; i--){
                if(high_price < prices[i])
                    high_price = prices[i];
                if(high_price - prices[i] > cur_profit)
                    cur_profit = high_price - prices[i];
                max_profit_reverse[i] = cur_profit;//存放从i到len-1之间，进行一次买卖的最大收益
            }
            int max = 0;
            for(int i = 0; i < len; i++){
                if(max < max_profit[i] + max_profit_reverse[i])
                    max = max_profit[i] + max_profit_reverse[i];
            }
            return max;
        }
    };

[https_leetcode.com_problems_best-time-to-buy-and-sell-stock-iii]: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
[http_blog.csdn.net_u010902721_article_details_45829153]: http://blog.csdn.net/u010902721/article/details/45829153