Slow but short accepted DP solution ,don't have to tackle some corner cases


  • 1
    P

    class Solution {

    public:

    int maxProfit(int k,vector<int>& prices){
    	if( k<1 )
    		return 0;
    	int n = prices.size();
    	int i,j;
    
    	// n day  and the most num of transaction is n/2;
    	int s = min(k,n/2);
    
    	vector<int> buy(s+1,INT_MIN);
    	vector<int> sell(s+1,0);
    	for(i=0;i<n;i++)
    	{
    		//when j > i/2+1, it is not nessesary to calc buy and sell
    		for(j=1;j<min(s,i/2+1)+1;j++)
    		{
    			buy[j]=max(buy[j],sell[j-1]-prices[i]);
    			sell[j]= max(buy[j]+prices[i],sell[j]);
    		}
    	}
    	return sell[s];
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.