Yet another Java O(n) time / O(1) space


  • 0

    Although my solution is not as awesome as this one, I decided to put it here anyway.

    public int maxProfit(int[] prices) {
        if (prices.length <= 1)
            return 0;
        int mpcla = 0; // max profit, closed long ago
        int mpcld = 0; // max profit, closed on the last day
        int mpplo = 0; // max profit, position left open
        int pose = 0; // for mpplo, the day of position opening
        int maxProfitMinusPrice = -prices[0];
        for (int i = 1; i < prices.length; ++i) {
            if (mpcla > mpplo) { // held position for too long, lost profit
                mpplo = mpcla;
                pose = i;
            } else { // position remains open, but maybe we can reopen it better?
                pose = prices[i] < prices[pose] ? i : pose;
            }
            mpcla = Math.max(mpcld, mpcla);
            mpcld = maxProfitMinusPrice + prices[i]; // sold on this day
            if (mpplo - prices[pose] > maxProfitMinusPrice) {
                maxProfitMinusPrice = mpplo - prices[pose]; // useful for selling later
            }
        }
        return Math.max(mpcla, mpcld);
    }
    

    The idea is as follows. For every given day we find three best profits:

    • the best profit we can have on that day if we sell before that day and don't buy anything (mpcla);
    • the best profit we can have on that day if we sell on exactly that day (mpcld);
    • the best profit we can have on that day and at the same time have an open long position (mpplo).

    For the last case, we also keep track of the best day for opening the position (pose). The answer will be the maximum between the first and the second values because we aren't exactly allowed to keep position open after the last day. Now for the updating rules:

    • mpcla is the most obvious: it's the best of all profits we could make before this day with the position closed, so it's the maximum of yesterday's mpcla and mpcld (because the last day is no longer the last).

    • mpcld is the most tricky: it's the maximum profit we can get by selling on this day, so it's actually the maximum of all mpplo[j] + (prices[i] - prices[pose[j]]) (we consider the profit we had with the position open plus the profit from our new sale) for all 0 <= j <= i - 1. However, note that only mpplo[j] and pose[j] depend on j so if we can calculate the maximum of the difference between these beforehand, we don't need another inner loop. And that's where maxProfitMinusPrice comes in.

    • We only update mpplo if we figure out that the profit we had for selling before yesterday (hence the not updated value of mpcla in the first if) outweighs the profit we had while keeping the position open, so we now change our decision, sell some day before yesterday, and then buy again today. And even if we keep mpplo the same, we may wish to reopen the position today if the price is better (the else part). Now both of these is something you unfortunately can't do in real life :-)


Log in to reply
 

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