If only trading stock is this easy ... :)


  • 0
    C
    public class Solution {
        int[] bestTrade(int p[], int b, int e, boolean sellShort) {
            int[] ret = new int[3];
            int entry = ret[1] = ret[2] = b;
            for (int i = b+1; i < e; ++i) {
                if ((!sellShort && p[i] <= p[entry]) ||
                     (sellShort && p[i] >= p[entry])) {
                    entry = i;
                }
                else {
                    int profit = p[i] - p[entry];
                    if (sellShort) profit = -profit;
                    if (profit > ret[0]) {
                        ret[0] = profit;
                        ret[1] = entry;
                        ret[2] = i;
                    }
                }
            }
            return ret;
        }
        public int maxProfit(int[] prices) {
            int[] tmp = bestTrade(prices, 0, prices.length, false);
            if (0 == tmp[0]) return 0;
            int profit = tmp[0]; int b = tmp[1]; int e = tmp[2]+1;
            tmp = bestTrade(prices, 0, b, false); int p1 = tmp[0];
            tmp = bestTrade(prices, b+1, e-1, true); int p2 = tmp[0];
            tmp = bestTrade(prices, e, prices.length, false); int p3 = tmp[0];
            return profit + Math.max(p1, Math.max(p2, p3));
        }
    }

Log in to reply
 

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