Extend most voted of III, O(kN) time, O(N) space, Java


  • 0
    P

    In below code, maxProfit_v0() is the base version, and maxProfit is space optimized version.
    buy[i][j]: most profit get from the first j days with at most i buy actions.
    sell[i][j]: most profit get from the first j days with at most i sell actions.

    public class Solution {
        public int maxProfit(int k, int[] prices) {
    		if (prices == null || prices.length < 2)
    			return 0;
    		if (k >= prices.length)
    			return maxProfitInfinite(prices);
    		int N = prices.length;
    		int[] sellOneLess = new int[N + 1];
    		int[] sell= new int[N + 1];
    		int[] buy = new int[N + 1];
    		for (int i = 1; i <= k; i++) {
    			sell[0] = 0;
    			buy[0] = Integer.MIN_VALUE;
    			for (int j = 1; j <= N; j++) {
    				sell[j] = Math.max(buy[j - 1] + prices[j - 1], sell[j - 1]);
    				buy[j] = Math.max(sellOneLess[j - 1] - prices[j - 1], buy[j - 1]);
    			}
    			for (int j = 0; j <= N; j++) {
    				sellOneLess[j] = sell[j];
    			}
    		}
    		return sell[N];
    	}
    	
        // base version of the above maxProfit()
        public int maxProfit_v0(int k, int[] prices) {
    		if (prices == null || prices.length < 2)
    			return 0;
    		if (k >= prices.length)
    			return maxProfitInfinite(prices);
    		int N = prices.length;
    		int[][] buy = new int[k + 1][N + 1];
    		int[][] sell = new int[k + 1][N + 1];
    		for (int i = 1; i <= k; i++) {
    			sell[i][0] = 0;
    			buy[i][0] = Integer.MIN_VALUE;
    			for (int j = 1; j <= N; j++) {
    				sell[i][j] = Math.max(buy[i][j - 1] + prices[j - 1], sell[i][j - 1]);
    				buy[i][j] = Math.max(sell[i - 1][j - 1] - prices[j - 1], buy[i][j - 1]);
    			}
    		}
    		return sell[k][N];
    	}
    	
    	public int maxProfitInfinite(int[] prices) {
    		int profit = 0;
    		for (int i = 1; i < prices.length; i++) {
    			profit += Math.max(prices[i] - prices[i - 1], 0);
    		}
    		return profit;
    	}
    }
    

Log in to reply
 

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