152. 乘积最大子数组

image.png

暴力

  1. func maxProduct1(nums []int) int {
  2.     max :=math.MinInt64
  3.     for i:=0;i<len(nums);i++{
  4.         var res =1
  5.         for j:=i;j<len(nums);j++{
  6.             res =res*nums[j]
  7.             if max<res{
  8.                 max =res
  9.             }
  10.         }
  11.     }
  12.     return max
  13. }

图片.png

动态规划

需要实现了动态转移 一个是当前最大值 一个是最小值 ，因为数组存在负数 ，当两个负数相乘为整数

  1. package main
  3. import (
  4.     "fmt"
  5.     "sort"
  6. )
  8. // 三个数字排列 获取最大值和最小值
  9. func search(a,b,c int)(big,small int){
  10.     i :=[]int{a,b,c}
  11.     sort.Ints(i)
  12.     return i[2],i[0]
  13. }
  14. func maxProduct(nums []int) int {
  15.    dpMax :=make([]int,len(nums))
  16.     dpMin:= make([]int,len(nums))
  17.     dpMax[0] =nums[0]
  18.     dpMin[0] = nums[0]
  19.    max :=nums[0]
  20.    for i:=1;i<len(nums);i++{
  21.      dpMax[i],dpMin[i] = search(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i],nums[i])
  22.        if dpMax[i]>max {
  23.            max = dpMax[i]
  24.        }
  25.     }
  26.     return max
  27. }
  28. func main() {
  29.     fmt.Println(maxProduct([]int{-2,0,-1}))
  30.     fmt.Println(maxProduct([]int{2,3,-2,4}))
  31.     fmt.Println(maxProduct([]int{-2,3,-4}))
  32. }

image.png