C++ Code (Time and Space optimized)


#1

int Solution::solve(vector &prices, int k) {

int n=prices.size();
if(n==0)return 0;

if(k>=n/2)
{
    //case where we have multiple transaction
    vector<int>sell(n,0);
    vector<int>buy(n,0);
    
    buy[0]=-prices[0];
    
    for(int i=1;i<n;i++)
    {
        sell[i]=max(sell[i-1],buy[i-1]+prices[i]);
        buy[i]=max(buy[i-1],sell[i-1]-prices[i]);
    }
    
    return sell[n-1];
}

//space optimization
vector<int>prev(n,0);
vector<int>curr(n,0);

for(int t=1;t<=k;t++)
{
    int maxsofar=INT_MIN;
    for(int d=1;d<n;d++)
    {
        maxsofar=max(maxsofar,prev[d-1]-prices[d-1]);
        curr[d]=max(curr[d-1],maxsofar+prices[d]);
    }
}

return curr[n-1];

}