using System;

public class Program

{

    public int MaxProfit(int[] prices) {

        if(prices.Length <= 1) {

            return 0;

        }

        // max profit from day 0 to day i and day i we do buy/sell

        int[] buy = new int[prices.Length];

        int[] sell = new int[prices.Length];

        // init in day 0 to buy stock

        buy[0] = -prices[0];

        for(int i = 1; i < prices.Length; i++) {

            // we can do nothing today, or sell in the day before yesterday

            buy[i] = Math.Max(buy[i - 1], (i - 2 >= 0 ? sell[i - 2] : 0) - prices[i]);

            // we can do nothing today, or buy in yesterday

            sell[i] = Math.Max(sell[i - 1], buy[i - 1] + prices[i]);

        }

        // best profit can only be selling stock in the last day

        return sell[prices.Length - 1];

    }

}