力扣hot100 乘积最大子数组 DP

Problem: 152. 乘积最大子数组

思路

👨?🏫 参考题解

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

💖 Code

public class Solution {
	public int maxProduct(int[] nums)
	{
		int n = nums.length;
		if (n == 0)
			return 0;
//		f[i][0]：以 nums[i] 结尾的连续子序列乘积最小值
//		f[i][1]：以 nums[i] 结尾的连续子序列乘积最大值
		int[][] f = new int[n][2];
		f[0][0] = nums[0];
		f[0][1] = nums[0];
		for (int i = 1; i < n; i++)
			if (nums[i] >= 0)// nums[i] 为正数
			{
				f[i][1] = Math.max(nums[i], f[i - 1][1] * nums[i]);
				f[i][0] = Math.min(nums[i], f[i - 1][0] * nums[i]);
			} else// nums[i] 为负数的情况
			{
				f[i][1] = Math.max(nums[i], f[i - 1][0] * nums[i]);// 负数乘于最小值 == 最大值
				f[i][0] = Math.min(nums[i], f[i - 1][1] * nums[i]);// 负数乘于最大值 == 最小值
			}
		int res = nums[0];
		for (int i = 0; i < n; i++)
			res = res > f[i][1] ? res : f[i][1];
		return res;
	}
}