// https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

// int dp[5005][5005];
class Solution {
public:
    int dp[5005][5005];
    int n=0;
    int fun(vector<int>& arr, int i, int j)
    {
        if(i>=n || j>=n) return 0;

        if(dp[i][j]!=-1) return dp[i][j];

        int buy = fun(arr, i,j+1);
        buy =max(buy, arr[j]-arr[i] + fun(arr,j+2,j+2));
        if(i==j)
        {
            buy = max(buy,fun(arr,i+1,j+1));
        }

        return dp[i][j] = buy;
    }

    int maxProfit(vector<int>& prices) {
        memset(dp,-1,sizeof(dp));
        n = prices.size();
        return fun(prices,0,0);
    }
};