8ms concise c++


  • 5
    K

    the if (k >= prices.size()/2) code block is just the solution to Best Time to Buy and Sell Stock II actually, because when k gets too big and prices is much smaller it will be much faster to calculate this way.

    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if (k == 0) return 0;
            if (k >= prices.size()/2) {
                int res = 0;
                for (int i = 1; i < prices.size(); ++i)
                    res += max(prices[i] - prices[i-1], 0);
                return res;
            }
            vector<int> buy(k, INT_MIN);
            vector<int> sell(k, 0);
            for (int price : prices)
                for (int i = 0; i < k; ++i) {
                    buy[i] = max(buy[i], (i > 0 ? sell[i-1] : 0) - price);
                    sell[i] = max(sell[i], buy[i] + price);
                }
            return sell.back();
        }
    };

  • 0
    Z

    the if (k >= prices.size()/2) code block is just the solution to Best Time to Buy and Sell Stock II actually -- excellent point!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.