题目(10¥)
题目地址:https://leetcode-cn.com/problems/maximum-product-subarray/
题解
动态规划题,这一题要注意区分两种情况,数的正负。
原本我们只需要一个的dp数组,这边需要两个,记录最优解(目前位置最大值,目前位置最小值)。
当前数为正数时,状态转移方程:
dpMax[i] = Math.max(dpMax[i - 1] * nums[i], nums[i])
当前数为负数时,状态转移方程:
dpMin[i] = Math.min(dpMin[i - 1] * nums[i], nums[i])
因为我们计算 dp[i] 的时候只关注 dp[i - 1] 所以可以简化空间复杂度到 O(1)。
源码
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] < 0) {
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax * nums[i], nums[i]);
imin = Math.min(imin * nums[i], nums[i]);
max = Math.max(max,imax);
}
return max;
}
}