【LeetCode精选TOP面试题】152-乘积最大子数组

LeetCode 原题链接

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个  32-位 整数。

子数组 是数组的连续子序列。

动态规划

思路

在一次遍历中不断维护到 i 为止的最大积 iMax、最小积 iMin，以及一个全局的最大积 max。

遇到负数时会让之前维护的最大乘积成为新的最小乘积，最小乘积成为新的最大乘积。

每遇到一个元素都更新 iMax、iMin 和 Max。

复杂度

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

代码

var maxProduct = function (nums) {
  let iMax = 1;
  let iMin = 1;
  let max = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i];
    if (num < 0) {
      [iMax, iMin] = [iMin, iMax];
    }
    iMax = Math.max(num * iMax, num);
    iMin = Math.min(num * iMin, num);
    max = Math.max(iMax, max);
  }
  return max;
};
let result = maxProduct([2, 3, -2, 4]);
console.log(result);