Maximum Product in Contiguous Array

给定一个数组 numbers，找出其中乘积最大的连续子数组，返回该子数组的乘积。

连续子数组的定义：[2, 3] 为 [1, 2, 3, 4] 子数组，而 [1, 3] 不是。

思路

数组中的负数会导致最大值变最小值翻转，因此需要同时维护两个状态。

使用动态规划，遍历数组时，维护：

maxProd：当前最大乘积
minProd：当前最小乘积

状态转移方程：

maxProd = max(num, num * prevMax, num * prevMin)
minProd = min(num, num * prevMax, num * prevMin)

遍历结束时，maxProd 就是最大乘积。

代码

function maxProductSubarray(numbers: number[]): number {
  if (numbers.length === 0) return 0;

  let maxProd = numbers[0];
  let minProd = numbers[0];
  let result = numbers[0];

  for (let i = 1; i < numbers.length; i++) {
    const num = numbers[i];

    if (num < 0) {
      // 负数时必须交换，因正负会互相翻转
      [maxProd, minProd] = [minProd, maxProd];
    }

    // 因为前面交换了，因此省略第三项
    maxProd = Math.max(num, maxProd * num);
    minProd = Math.min(num, minProd * num);

    result = Math.max(result, maxProd);
  }

  return result;
}

Maximum Product in Contiguous Array

思路

代码

目录