Maximum Product Subarray leetcode - Ryan的修炼之路

Find the contiguous subarray within an array (containing at least one
number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3]
has the largest product = 6.

动态规划

思路

state: max[i]min[i]分别表示前i步的最大最小值
function: 因为乘积有正负之分, 有可能一个大数是由两个负数相乘而得来所以这里为我们记录一个乘积的最大值max也记录一个乘积的最小值min
每一步的最大值取 max[i-1] nums[i], min[i - 1] nums[i] 和nums[i]之间最大的, 最小值是取三个中最小的
intialize: max[0], min[0]都等于数组第一个值
answer: res

复杂度

时间O(n) 空间O(n)/O(1)

代码

//space O(n)public int maxProduct(int[] nums) {    if (nums.length == 0) {        return 0;    }    int len = nums.length;    int[] max = new int[len];    int[] min = new int[len];    max[0] = min[0] = nums[0];    int res = max[0];    for (int i = 1; i < len; i++) {max[i] = Math.max(Math.max(nums[i], max[i-1] * nums[i]), min[i-1] * nums[i]);        min[i] = Math.min(Math.min(nums[i], min[i-1] * nums[i]), max[i-1] * nums[i]);        res = Math.max(res, max[i]);    }    return res;}//space O(1)public int maxProduct(int[] nums) {    if (nums == null || nums.length == 0) {        return 0;    }    int max = nums[0];    int min = nums[0];    int res = nums[0];    for (int i = 1; i < nums.length; i++) {        int a = max * nums[i];        int b = min * nums[i];        max = Math.max(nums[i], Math.max(a, b));        min = Math.min(nums[i], Math.min(a, b));        res = Math.max(res, max);    }    return res;}