
乘积最大子数组
解法:动态规划
思路:
- 遍历数组时计算当前最大值,不断更新。
- 不要漏掉负负得正的情况
代码:
/** * @question 乘积最大子数组 * @param {number[]} nums * @return {number} */ const maxProduct = (nums) => { let res = nums[0] let prevMin = nums[0] let prevMax = nums[0] let tempMin = 0, tempMax = 0 for (let i = 1; i < nums.length; i++) { tempMin = prevMin * nums[i] tempMax = prevMax * nums[i] prevMin = Math.min(tempMax, tempMin, nums[i]) prevMax = Math.max(tempMax, tempMin, nums[i]) // 此处容易忽略负负得正的情况 res = Math.max(prevMax, res) } return res }
评论(0)