Any solutions better than O(n^2)


  • 9
    A

    My idea:

    1) Find all valley and peek pairs (buy at valley point and sell at peek point) . ( in O(n) time)

    input: 6 1 3 2 4 7 6 10 15

    output of this step: (1, 3), (2,7), (6, 15)

    2) Find the split point that maximize profit, since we can complete at most two transactions. (in O(m^2), m is the number of pairs generated in step 1)

    total_profit = 0

    for i =0 to m-1:

     first transaction complete before pair[i] ( include pair[i])
        compute max profit of the first transaction in O(i)
     second transaction complete after pair[i] (exclude pair[i])
        compute max profit of the second transaction in O(m-i)
     total_profit = max( total_profit, first + second)
    

    my accepted code:

    int maxProfit(vector<int> &prices) {
            // step 1, find pairs
            vector<int> lows;  // local low points
            vector<int> highs; // local peek points
            
            int n = prices.size();
            int i = 0;
            while(i < n) {
                while(i+1<n && prices[i+1] <= prices[i]) ++i;
                lows.push_back(prices[i]);
                
                while(i+1<n && prices[i+1] >= prices[i]) ++i;
                highs.push_back(prices[i]);
                
                ++i;
            }
            
            // step 2: split
            int total_profit = 0;
            n = lows.size();
            for (i = 0; i < n; ++i) {
                int j = 0;
                int low = INT_MAX;
                int high = 0;
                int first = 0;   // max profit of the first transaction
                int second = 0;  // max profit of the second transaction
                while (j <= i) {
                    low = min(low, lows[j]);
                    high = highs[j];
                    first = max(first, high-low);
                    ++j;
                }
                
                low = INT_MAX;
                high = 0;
                j = i+1;
                while (j < n) {
                    low = min(low, lows[j]);
                    high = highs[j];
                    second = max(second, high - low);
                    ++j;
                }
                total_profit = max(total_profit, first + second);
            }
            
            return total_profit;
        }
    

    I think there are better solutions, but I haven't got it - -
    Anybody has one to share ?


  • 89
    S

    Here is an answer by Eric from old discuss. Thanks to Eric.

    First consider the case that when we are only allowed to make one transaction. we can handle this easily with DP. If we move forward, any new price we meet will only affect our history result by two ways:

    will it be so low that it beats our previous lowest price?
    will it be so high that we should instead sell on this time to gain a higher profit (than the history record)? Similarly, we can move backward with the highest price and profit in record. Either way would take O(n) time.
    Now consider the two transaction case. Since there will be no overlaps, we are actually dividing the whole time into two intervals.

    We want to maximize the profit in each of them so the same method above will apply here. We are actually trying to break the day at each time instance, by adding the potential max profit before and after it together. By recording history and future for each time point, we can again do this within O(n) time.

    class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            // null check
            int len = prices.size();
            if (len==0) return 0;
    
            vector<int> historyProfit;
            vector<int> futureProfit;
            historyProfit.assign(len,0);
            futureProfit.assign(len,0);
            int valley = prices[0];
            int peak = prices[len-1];
            int maxProfit = 0;
    
            // forward, calculate max profit until this time
            for (int i = 0; i<len; ++i)
            {
                valley = min(valley,prices[i]);
                if(i>0)
                {
                    historyProfit[i]=max(historyProfit[i-1],prices[i]-valley);
                }
            }
    
            // backward, calculate max profit from now, and the sum with history
            for (int i = len-1; i>=0; --i)
            {
                peak = max(peak, prices[i]);
                if (i<len-1)
                {
                    futureProfit[i]=max(futureProfit[i+1],peak-prices[i]);
                }
                maxProfit = max(maxProfit,historyProfit[i]+futureProfit[i]);
            }
            return maxProfit;
        }
    };

  • 0
    A

    Nice work!
    I have thought about solve forward in O(n),
    but haven't realized that backward can use the same method!


  • 0
    L

    Here is a solution with O(n) time complexity and O(1) space complexity, inspired by Maximum subarray problem (http://en.wikipedia.org/wiki/Maximum_subarray_problem).

    The idea is looking at the delta price series and find two non-overlap subarrays that leads to the maximum sum.

    class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            int one[] = {-1, -1}, two[] = {-1, -1};
            int profit[] = {0, 0};
            int mergeProfit = 0;
            int i = 1, currDelta = 0;
            bool isOneDone = false;
            // find the initial two profitable transactions as base.
            for (; i < prices.size(); ++i) {
                currDelta = prices[i] - prices[i-1];
                if (one[0] == -1 && currDelta <= 0) {
                    continue;
                } else if (one[0] == -1 && currDelta > 0) {
                    one[0] = one[1] = i;
                    mergeProfit = profit[0] = currDelta;
                    continue;
                } else if (one[0] != -1 && !isOneDone && currDelta < 0) {
                    isOneDone = true;
                    mergeProfit += currDelta;
                } else if (one[0] != -1 && !isOneDone && currDelta >= 0) {
                    one[1] = i;
                    profit[0] = (mergeProfit += currDelta);
                } else if (isOneDone && two[0] == -1 && currDelta < 0) {
                    mergeProfit += currDelta;
                } else if (isOneDone && two[0] == -1 && currDelta >= 0) {
                    two[0] = two[1] = i;
                    mergeProfit += currDelta;
                    profit[1] = currDelta;
                } else if (isOneDone && two[0] != -1 && currDelta >=0) {
                    mergeProfit += currDelta;
                    profit[1] += currDelta;
                    two[1] = i;
                } else if (isOneDone && two[0] != -1 && currDelta < 0) {
                    break;
                }
            }
            if (i >= prices.size()) {
                return profit[0] + profit[1];
            }
    
            // for any price after the current best transactions,
            // find the maximum subarray of delta price then comparing the
            // four possible ways to merge into current two transactions.
            // If it yields a better profit update the current best transactions.
            int currMax = 0;
            int currMaxStart = -1, currMaxEnd = -1;
            int currAdded = 0;
            int currStart = -1;
            int currAddedTotal = 0;
            for (; i < prices.size(); ++i) {
                currDelta = prices[i] - prices[i-1];
                currAdded += currDelta;
                currAddedTotal += currDelta;
                if (currAdded <= 0) {
                    currAdded = 0;
                    currStart = -1;
                    continue;
                } else if (currStart == -1) {
                    currStart = i;
                }
                if (currMax >= currAdded) {
                    continue;
                } 
                currMax = currAdded;
                currMaxStart = currStart;
                currMaxEnd = i;
                int currProfit = profit[0] + profit[1];
                int A_C = profit[0] + currMax;
                int AB_C = mergeProfit + currMax;
                int A_BC = profit[0] + profit[1] + currAddedTotal;
                int B_C = profit[1] + currMax;
                if (B_C >= currProfit && B_C >= A_BC && B_C >= AB_C && B_C >= A_C) {
                    mergeProfit = profit[1] + currAddedTotal;
                    one[0] = two[0];
                    one[1] = two[1];
                    profit[0] = profit[1];
                    two[0] = currMaxStart;
                    two[1] = currMaxEnd;
                    profit[1] = currMax;
                } else if (AB_C >= currProfit && AB_C >= A_C && AB_C >= A_BC && AB_C >= B_C) {
                    one[1] = two[1];
                    two[0] = currMaxStart;
                    two[1] = currMaxEnd;
                    profit[0] = mergeProfit;
                    profit[1] = currMax;
                    mergeProfit = mergeProfit + currAddedTotal;
                } else if (A_BC >= currProfit && A_BC >= B_C && A_BC >= AB_C && A_BC >= A_C) {
                    two[1] = currMaxEnd;
                    profit[1] = profit[1] + currAddedTotal;
                    mergeProfit = mergeProfit + currAddedTotal;
                } else if (A_C >= currProfit && A_C >= AB_C && A_C >= A_BC && A_C >= B_C) {
                    two[0] = currMaxStart;
                    two[1] = currMaxEnd;
                    profit[1] = currMax;
                    mergeProfit = mergeProfit + currAddedTotal;
                } else {
                    continue;
                }
                currMax = 0;
                currMaxStart = -1, currMaxEnd = -1;
                currAdded = 0;
                currStart = -1;
                currAddedTotal = 0;
            }
            return profit[0] + profit[1];
        }
    };
    

  • 14
    Q

    There is a general case algorithm. It can solve the max profit of k transactions in O(kn). Here is the C++ code according to this paper. "Maximum-Scoring Segment Sets - Miklo ́s Csu ̋ro ̈s 1"

    int maxProfit(vector<int> &prices) {
        vector<bool> segs(prices.size());
        int maxprofit = 0;
        for (int transact = 0; transact < 2; ++transact) {
            int i0 = 0, c = 0, cmax = 0;
            vector<int> s;
            for (int i = 0; i < (int)prices.size()-1; ++i) {
                if (i > 0 && segs[i] != segs[i-1]) {
                    i0 = i; c = 0;
                }
                c = c + prices[i+1] - prices[i];
                if ((!segs[i] && c <= 0) || (segs[i] && c >= 0)) {
                    i0 = i+1; c = 0;
                } else if (cmax < abs(c)) {
                    cmax = abs(c); s = {i0, i};
                }
            }
            if (cmax == 0) break;
            for (int i = s[0]; i <= s[1]; ++i) segs[i] = !segs[i];
            maxprofit += cmax;
        }
        return maxprofit;
    }
    

  • 0
    R

    One doubt: if the maxprofit is for day i, does not it mean that we are selling the first share on day i (which we bought at earlier day) and then buying a share again on day i (and selling it some later day) - an overlap? Am I missing something? Although it seems that the history profit peak and future profit valley can not occur on the same day.


  • 0
    O

    I think if getting maxprofit on day i does not necessarily mean we are selling the first share on the day and then buying it. history[i] is the peak profit we can made on day i, but we might have sold it on earlier day.
    And the last sentence in your comment is not clear to me. We are getting the max history profit and the max future profit.
    The solution is so elegant although I think we does not have to maintain futureProfit[i].


  • 0
    R

    I understand that solution for day i does not necessarily mean that we are selling the first share on day i, but we may. For the final pass, I did something like the following and OJ accepted my code. I hope it makes clear what I am trying to say (sorry for the formatting, I dont know how to format it properly).

    maxProfit = futureProfit[0];
    for(int i= 0; i<days-1; i++)
    if(historyProfit[i]+futureProfit[i+1] > maxProfit)
    maxProfit = historyProfit[i]+futureProfit[i+1];

    if(historyProfit[days-1] > maxProfit)
    maxProfit = historyProfit[days-1];


  • 0
    I

    I am using this approach in Python and get "Time limit exceeded" for a large input.


  • 0
    P

    hi invain, my python code with the solution provided by Shangrila got accepted with 332 ms, you might have ran into infinite loop while executing your code?


  • 0
    W

    Would you like to explain this code?


  • 0
    Q

    You can read the paper "Maximum-Scoring Segment Sets", it explains the algorithm in details. There are a few lemmas needed to prove this algorithm, I understood it before, but I cannot explain it now without reviewing this paper first.


  • 0
    W

    Would the forward passing and backward passing find the same valley and same peak?


  • 0
    Z

    solved.............


  • 0
    C
    public class BuyStock3 {
    public static int maxProfit(int[] prices) {
    	int n = prices.length;
    	if (n == 0)
    		return 0;
    	int[] ltoR = new int[n];
    	ltoR[0] = 0;
    	int[] rtoL = new int[n];
    	int[] lmin = new int[n];
    	lmin[0] = prices[0];
    	int[] rmax = new int[n];
    	rmax[n - 1] = prices[n - 1];
    	int maxP = 0;
    
    	for (int i = 1; i < n; i++) {
    		// min price from left to right
    		lmin[i] = Math.min(lmin[i - 1], prices[i]);
    		// max price from right to left
    		rmax[n - i - 1] = Math.max(rmax[n - i], prices[n - i - 1]);
    		// max profit from left to right
    		ltoR[i] = Math.max(ltoR[i - 1], prices[i] - lmin[i]);
    		// max profit from right to left
    		rtoL[n - i - 1] = Math.max(rtoL[n - i], rmax[n - i - 1]
    				- prices[n - i - 1]);
    	}
    	for (int i = 0; i < n; i++) {
    		// combine two transaction by getting the profit from two side
    		maxP = Math.max(maxP, ltoR[i] + rtoL[i]);
    	}
    	return maxP;
    }
    
    public static void main(String[] args) {
    	int[][] test = { { 2, 1, 2, 0, 1 }, { 1 }, { 1, 2, 3, 1, 2, 3 } };
    	for (int[] t : test) {
    		System.out.println(maxProfit(t));
    	}
    }
    

    }

    1.find first trade from left to right
    2.find second trade from right to left
    3.find max profit by combine them.


  • 0
    R

    you do not need to use a vector to save the results for the backward case, you just need the previous results.


  • 2
    J

    Here is a solution with O(n) space and O(n) time.

    One observation is that the two transactions do not overlap. One transaction must be the max transaction between day 0 and day i, save it as maxBy[i]; another must be the max transaction between day i+1 and day prices.size()-1, save it as maxSince[i+1]. Scanning from left to right gets us maxBy[], and scanning right to left gets us maxSince[].

    The max single-transaction profit is either maxSince[0] or the last maxBy[].

    Next we just need to find i such that maxBy[i]+maxSince[i+1] is the max two-transaction profit.


  • 1
    J
    public static int maxProfit1(int[] prices) {
        if(prices.length < 2)
            return 0;
        int len = prices.length;
        int[] profits = new int[len];
        int min = prices[0];
        for(int i=1; i<len; i++){
            int profit = prices[i] - min;
            profits[i] = Math.max(profits[i-1], profit);
            min = Math.min(min, prices[i]);
        }
        
        int maxProfit = profits[len-1];
        profits[len-1] = 0;
        int max = prices[len-1];
        for(int i=len-2; i>=0; i--){
            int profit = max - prices[i];
            profit = Math.max(profits[i+1], profit);
            max = Math.max(max, prices[i]);
            int totalProfit = profit + profits[i];
            if(totalProfit > maxProfit)
                maxProfit = totalProfit;
            profits[i] = profit;
            
        }
        
        return maxProfit;
    }

  • 0
    G

    my idea is much same as the best answer , maybe a little bit different
    i feel so excited that i work it out myself , here's my code just for reference(28ms)

    class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            if (prices.size()<=1) return 0;
            int low = prices[0];
            int h = 0,profit = 0;
            vector<int> d(prices.size(),0);// marks the best option in day0 ~ dayi
            vector<int> e(prices.size(),0);// marks the best option in dayi ~ end
            vector<int> high(prices.size(),0);// high[i] represents the highest price in dayi ~ end
            
            for (int i=prices.size()-1;i>0;i--){
                h= max(h,prices[i]);
                high[i] = h;
                if (i<prices.size()-1) 
                    e[i] = max(e[i+1],h - prices[i]);
            }
                
            for (int i=1;i<prices.size();i++){
                low = min(low,prices[i]);
                d[i] = max(d[i-1],prices[i]-low);
                profit = max(profit,max(d[i]+e[i],high[i]-low));//not sure to call it DP
            }
            
            return profit;
        }
    };

  • 0
    N

    Great solution. What about the situation that "You may complete more than two transactions ?" or "You may complete transactions as many as possible?"


Log in to reply
 

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