152. 乘积最大子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。思路
DP 方程需要两个维度
// DP[i, 0], DP[i, 1] , 0 表示 max, 1 表示 min
if a[i] >= 0:
DP[i, 0] = DP[i - 1, 0] * a[i]
DP[i, 1] = DP[i - 1, 1] * a[i]
else:
DP[i, 0] = DP[i - 1, 1] * a[i]
DP[i, 1] = DP[i - 1, 0] * a[i]优化:
要保存最大值， 最小值。因为负负得正解法一
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if nums is None: return 0
dp = [[0 for _ in range(2)] for _ in range(2)]
dp[0][1], dp[0][0], res = nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
x, y = i % 2, (i - 1) % 2 # 滚动数组
dp[x][0] = max(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])
dp[x][1] = min(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])
res = max(res, dp[x][0])
return res
class Solution {
public int maxProduct(int[] nums) {
int min = nums[0], max = nums[0], result = nums[0];
for (int i = 1; i < nums.length; i++) {
if(nums[i] < 0) {
int tmp = 0;
tmp = min;
min = max;
max = tmp;
}
min = Math.min(min * nums[i], nums[i]);
max = Math.max(max * nums[i], nums[i]);
result = Math.max(result, max);
}
return result;
}
}
class Solution:
def maxProduct(self, nums: List[int]) -> int:
mi = ma = res = nums[0]
for i in range(1, len(nums)):
if nums[i] < 0: mi, ma = ma, mi
ma = max(ma * nums[i], nums[i])
mi = min(mi * nums[i], nums[i])
res = max(res, ma)
return res
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if nums is None: return 0
res, curMax, curMin = nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
num = nums[i]
curMax, curMin = curMax * num, curMin * num
curMin, curMax = min(curMax, curMin, num), max(curMax, curMin, num)
res = curMax if curMax > res else res
return res