152.乘积最大子数组.md

152.乘积最大子数组

/*
 * @lc app=leetcode.cn id=152 lang=typescript
 *
 * [152] 乘积最大子数组
 */

// @lc code=start
function maxProduct(nums: number[]): number {}
// @lc code=end

解法 1: 动态规划

• 时间复杂度:
• 空间复杂度:

同时记录最大乘积和最小乘积

function maxProduct(nums: number[]): number {
  let [max, imin, imax] = [nums[0], nums[0], nums[0]]
  for (let i = 1; i < nums.length; i++) {
    ;[imin, imax] = [
      Math.min(imin * nums[i], nums[i], imax * nums[i]),
      Math.max(imax * nums[i], nums[i], imin * nums[i]),
    ]
    max = Math.max(max, imax)
  }
  return max
}

解法 2: 前后两次遍历

• 时间复杂度:
• 空间复杂度: <img style="transform: translateY(0.1em); background: white;" src="./svg/o-1.svg" alt="O(1)"

如果数组中没有零,则数组中乘积的最大值,必然是从第一个元素开始,或者从最后一个元素开始,分别从前往后和从后往前累计乘积,并记录最大值

• https://leetcode.com/problems/maximum-product-subarray/discuss/183483/JavaC%2B%2BPython-it-can-be-more-simple

function maxProduct(nums: number[]): number {
  let [res, prefix, suffix] = [nums[0], 0, 0]
  for (let i = 0; i < nums.length; i++) {
    prefix = (prefix === 0 ? 1 : prefix) * nums[i]
    suffix = (suffix === 0 ? 1 : suffix) * nums[nums.length - 1 - i]
    res = Math.max(res, prefix, suffix)
  }
  return res === -0 ? 0 : res
}

Case

test.each([
  { input: { nums: [2, 3, -2, 4] }, output: 6 },
  { input: { nums: [2, -3, -2, 4] }, output: 48 },
  { input: { nums: [-2, 0, -1] }, output: 0 },
  { input: { nums: [-3, -1, -1] }, output: 3 },
  { input: { nums: [-2] }, output: -2 },
  { input: { nums: [-2, 3, -4] }, output: 24 },
  { input: { nums: [-4, -3, -2] }, output: 12 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(maxProduct(nums)).toBe(output)
})