D&C solution but got TLE


  • 0
    F

    Got TLE but I think it provides food for thought

    We look at the maximum profit one can make in a range. Since there's need to cooldown for one day, we just try to pick each day to break the range and find the result of left/right part. Note that another possible solution is not divide for a range, e.g to get profit by range[right]-range[left]

    int[][] buf;
    public int maxProfit(int[] prices) {
    	buf = new int[prices.length][prices.length];
    	return doShit(prices, 0, prices.length - 1);
    }
    
    int doShit(int[] prices, int start, int end) {
    	if (start < 0 || start >= prices.length || end < 0 || end >= prices.length) {
    		return 0;
    	}
    	if (buf[start][end] > 0) {
    		return buf[start][end];
    	}
    	if (end <= start) {
    		return 0;
    	}
    
    	// don't divide
    	int ret = prices[end] > prices[start] ? prices[end] - prices[start] : 0;
    	// divide at each point
    	for (int i = start; i <= end; i++) {
    		ret = Math.max(ret, doShit(prices, start, i - 1) + doShit(prices, i + 1, end));
    	}
    	buf[start][end] = ret;
    	return ret;
    }

Log in to reply
 

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