Why don't we make our life easier


  • 9
    J

    The idea is very basic. At most two transactions means we can break at any time point and compute the max revenue before this time point and after this time point. For every possible time point, we choose the maximum.

    Note that right_max start from the last time point, which is just like a mirror algorithm from the Best Time to Buy and Sell Stock I

    int maxProfit(vector<int>& prices) {
        vector<int> left_max;
        vector<int> right_max;
        int n = prices.size();
        if(n == 0){
            return 0;
        }
        int cur_min = prices[0];
        int max_r = 0;
        for(int i = 0; i < n; i++){
            max_r = max(max_r, prices[i] - cur_min);
            left_max.push_back(max_r);
            cur_min = min(cur_min, prices[i]);
        }
        int cur_max = prices[n-1];
        max_r = 0;
        for(int i = n-1; i >= 0; i--){
            max_r = max(max_r, cur_max - prices[i]);
            right_max.insert(right_max.begin(), max_r);
            cur_max = max(cur_max, prices[i]);
        }
        int sum_max = 0;
        for(int i = 0; i < n; i++){
            sum_max = max(sum_max, left_max[i] + right_max[i]);
        }
        return sum_max;
    }

  • 0
    F

    Really brilliant solution,thanks for sharing


  • 0
    L

    I come up something really close to you. But I want to point out that, the loop index of the last loop may not be right. In your code, left_max[i] and right_max[i] always have one overlapped item, which is prices[i]. I think the right thing to do is left_max[i] + right_max[i + 1]. Then, for i = n -1, something special need to be done. Both solutions can pass the Leetcode OJ, but i think the overlap takes some risk. Logically, the chance for the overlapped item to be used by both right and left sequence is low, but still the rick is there.


  • 0
    L

    I like your solution though it can not apply in k transactions.


  • 0
    X

    are you sure your solution is OK? the boundary seems not correct. Please check it again with case.


  • 0
    M

    @lanshan317 We could append a 0 at the end of right_max and as you said use
    sum_max = max( sum_max, left_max[i] + right_max[i+1] );


  • 0
    W

    Great idea. This is basically the same as 121. Best Time to Buy and Sell Stock. We do it from left to right, then right to left. Here is my Java version

    class Solution {
        public int maxProfit(int[] prices) {
            int len = prices.length;
            int[] left = new int[len];
            int[] right = new int[len];
            int buy = Integer.MAX_VALUE, max = 0;
            for (int i = 0; i < len; i++) {
                if (prices[i] < buy) {
                    buy = prices[i];
                } else {
                    max = Math.max(max, prices[i] - buy);
                }
                left[i] = max;
            }
            int sell = Integer.MIN_VALUE; 
            max = 0;
            for (int i = len - 1; i >= 0; i--) {
                if (prices[i] > sell) {
                    sell = prices[i];
                } else {
                    max = Math.max(max, sell - prices[i]);
                }
                right[i] = max;
            }
            int res = 0;
            for (int i = 0; i < len; i++) {
                res = Math.max(res, left[i] + right[i]);
            }
            return res;
        }
    }
    

Log in to reply
 

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