AC java solution that beat 96.90%


  • 0
    L
    public int maxProfit(int k, int[] prices) {
            if(k>prices.length/2){
    			int ans = 0;
    			for(int i=1;i<prices.length;i++)
    				if(prices[i]>prices[i-1])
    					ans+=prices[i]-prices[i-1];
    			return ans;
    		}
            int[] local = new int[k+1];
            int[] global = new int[k+1];
            for(int i=0;i<prices.length-1;i++){
            	int diff = prices[i+1]-prices[i];
            	for(int j=k;j>0;j--){
            		local[j] = Math.max(global[j-1]+(diff<0?0:diff), local[j]+diff);
            		global[j] = Math.max(global[j], local[j]);
            	}
            }
            return global[k];
        }
    

Log in to reply
 

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