/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	}
 
    public int maxProfit(int[] prices) {
        int n = prices.length;
 
        int rest = 0;
        int sold = 0;
        int held = 0 - prices[0];
 
        int prevHeld = held;
        int prevRest = rest;
        int prevSold = sold;
        for (int i = 1 ; i < n ; i++) {
 
            held = Math.max(prevRest - prices[i], prevHeld);
            sold = prevHeld + prices[i];
            rest = Math.max(prevRest, prevSold);
 
            prevHeld = held;
            prevSold = sold;
            prevRest = rest;
        }
 
        return Math.max(rest, sold);
    }
 
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCX0KCQogICAgcHVibGljIGludCBtYXhQcm9maXQoaW50W10gcHJpY2VzKSB7CiAgICAgICAgaW50IG4gPSBwcmljZXMubGVuZ3RoOwoKICAgICAgICBpbnQgcmVzdCA9IDA7CiAgICAgICAgaW50IHNvbGQgPSAwOwogICAgICAgIGludCBoZWxkID0gMCAtIHByaWNlc1swXTsKCiAgICAgICAgaW50IHByZXZIZWxkID0gaGVsZDsKICAgICAgICBpbnQgcHJldlJlc3QgPSByZXN0OwogICAgICAgIGludCBwcmV2U29sZCA9IHNvbGQ7CiAgICAgICAgZm9yIChpbnQgaSA9IDEgOyBpIDwgbiA7IGkrKykgewoKICAgICAgICAgICAgaGVsZCA9IE1hdGgubWF4KHByZXZSZXN0IC0gcHJpY2VzW2ldLCBwcmV2SGVsZCk7CiAgICAgICAgICAgIHNvbGQgPSBwcmV2SGVsZCArIHByaWNlc1tpXTsKICAgICAgICAgICAgcmVzdCA9IE1hdGgubWF4KHByZXZSZXN0LCBwcmV2U29sZCk7CgogICAgICAgICAgICBwcmV2SGVsZCA9IGhlbGQ7CiAgICAgICAgICAgIHByZXZTb2xkID0gc29sZDsKICAgICAgICAgICAgcHJldlJlc3QgPSByZXN0OwogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIE1hdGgubWF4KHJlc3QsIHNvbGQpOwogICAgfQoKfQ==