最大子数组乘积
# 📃 题目描述
题目链接:152. 乘积最大子数组 (opens new window)
# 🔔 解题思路
按照 53. 最大子数组和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 这题的思路去做的话,即 dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]),这样会出现问题!
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// nums[i] 左边的最大乘积
int[] maxDp = new int[nums.length];
// nums[i] 左边的最小乘积
int[] minDp = new int[nums.length];
// base case
maxDp[0] = nums[0];
minDp[0] = nums[0];
int res = maxDp[0];
for (int i = 1; i < nums.length; i ++) {
maxDp[i] = Math.max(Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
minDp[i] = Math.min(Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
res = Math.max(maxDp[i], res);
}
return res;
}
}
状态压缩:
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// nums[i] 左边的最大乘积
int preMax = nums[0];
// nums[i] 左边的最小乘积
int preMin = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; i ++) {
int curMax = Math.max(Math.max(preMax * nums[i], preMin * nums[i]), nums[i]);
int curMin = Math.min(Math.min(preMax * nums[i], preMin * nums[i]), nums[i]);
res = Math.max(res, curMax);
preMax = curMax;
preMin = curMin;
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10