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

• 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 :-)

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