写出了,暴力递归。使用二维数组做缓存,结果最后一条case,超出内存限制。
private int recursion(int[] nums, int[][] mem, int start, int end) {
if (start >= nums.length || end >= nums.length) {
return 0;
}
if (mem[start][end] != 0) {
return mem[start][end];
}
int result = nums[start];
for (int i = start + 1; i <= end; i++) {
result = nums[i] * result;
}
int row = recursion(nums, mem, start, end + 1);
int col = recursion(nums, mem, start + 1, end);
mem[start][end] = Math.max(row, Math.max(col, result));
return mem[start][end];
}
public int maxProduct(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int[][] mem = new int[nums.length][nums.length];
return recursion(nums, mem, 0, 0);
}
展开