# D&C solution but got TLE

• 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;
}

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