Really nice problem. DP Solution. Constant space and O(number_of_days) time


#1

int Solution::maxProfit(const vector &A)
{
int max_tran=2,no_of_days=A.size();
if(no_of_days<=1)
return 0;
vector<vector> dp(max_tran+1,vector(no_of_days,0));
for(int i=1;i<=max_tran;i++)
{
int max_diff=-A[0];
for(int j=0;j<no_of_days;j++)
{
dp[i][j]=max(max_diff+A[j],dp[i][j-1]);
max_diff=max(max_diff,dp[i-1][j]-A[j]);
}
}
return dp[max_tran][no_of_days-1];
}


#2

I am confused. What is this line if the solution is constant space??