Eusy and intutive soultion


#1

just identify dp state and the problem becomes easy for you.

-> find min price to buy and max price to sell that’s it.

int Solution::maxProfit(const vector<int> &A) {
    int n=A.size();
    int dp[n+1][3][2]={};
    
    // dp[n][i][j] -> dp state n = on nth day.
    // i = ith transaction
    // j=0 means buy, j=1 sell
    
    dp[0][1][0] = numeric_limits<int>::max();
    dp[0][2][0] = numeric_limits<int>::max();
    
    for(int i=0; i<n; i++){
        dp[i+1][1][0] = min(dp[i][1][0], A[i]);
        dp[i+1][1][1] = max(dp[i][1][1], A[i]-dp[i][1][0]);
        
        dp[i+1][2][0] = min(dp[i][2][0], A[i]-dp[i][1][1]);
        dp[i+1][2][1] = max(dp[i][2][1], A[i]-dp[i][2][0]);
    }
    
    return dp[n][2][1];
}