Skip to main content

2-29 152. 乘积最大的子数组

Date：2022-03-06 20:01:10

题目：152. 乘积最大的子数组 ( 中等😕 )​

动态规划

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

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

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

示例​

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是连续子数组。

所需基础​

  • 动态规划

    什么是动态规划（Dynamic Programming）？动态规划的意义是什么？.https://www.zhihu.com/question/23995189

    该文章有一个关于凑硬币的问题，有三种面值（1,5,11），给定一个数量K，找出最少数量凑出K值的方式

    比如：K=15，则最少数量为3，即（5,5,5）三张5元的

分析​

该题可以采用：1.暴力法 2.动态规划

  • 暴力法比较好想，只是会超过时间限制

  • 该题的动态规划比 扩展1：53. 最大子数组和 要难一些，主要要处理 [1,2,-3,4,-5] 这种包含多个负号的问题，详细推论见 乘积最大子数组

题解​

暴力法

function maxProduct(nums: number[]): number {
  let res = -Infinity

  for (let i = 0; i < nums.length; ++i) {
    let mul = nums[i]
    res = Math.max(res, mul)

    for (let j = i + 1; j < nums.length; ++j) {
      mul *= nums[j]

      res = Math.max(res, mul)
    }
  }

  return res == -Infinity ? undefined : res
}

动态规划

function main() {
  // const nums = [2, 3, -2, 4]
  // const nums = [-2, 0, -1]
  // const nums = []
  // const nums = [-2]
  const nums = [-3, 0, 1, -2]

  // console.log('[]:', maxProduct(nums))
  console.log('[]:', maxProduct111(nums))
}

[1,5,11]
15

f(15) = min(f(15-1), f(15-5), f(15-11))
f(n) = min(f(n-1), f(n-5), f(n-11))

minF = []

minF[i] = Math.min(f)

main()

function maxProduct111(nums: number[]): number {
  const len = nums.length
  let maxF = new Array(len).fill(0)
  let minF = new Array(len).fill(0)

  maxF[0] = nums[0]
  minF[0] = nums[0]

  for (let i = 1; i < len; ++i) {
    maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(minF[i - 1] * nums[i], nums[i]))
    minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(maxF[i - 1] * nums[i], nums[i]))
  }

  let res = maxF[0]
  for (let i = 1; i < len; ++i) {
    res = Math.max(res, maxF[i])
  }

  return res
}

扩展1：53. 最大子数组和 ( 简单😄 )​

动态规划

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

分析：可以采用 1.暴力法 2.动态规划

题解

暴力法

function maxSubArray(arr: number[]): number {
  let max = -Infinity

  for (let i = 0; i < nums.length; ++i) {
    let sum = 0
    for (let j = i; j < nums.length; ++j) {
      sum += nums[j]
      max = Math.max(max, sum)
    }
  }

  return max
}

动态规划

function main() {
  const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

  console.log('[]:', maxSubArray(arr))
}

main()

function maxSubArray(arr: number[]): number {
  let max = arr[0]
  let pre = arr[0]

  for (let i = 0; i < arr.length; ++i) {
    pre = Math.max(pre + arr[i], arr[i])
    max = Math.max(max, pre)
  }

  return max
}