008.乘积最大子数组

• 152.乘积最大子数组
  • 动态规划

乘积最大子数组 - 动态规划

func maxProduct(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	// dp[i]: 以 i 结尾
	dp := [2]int{
		nums[0], // 子数组最大乘积
		nums[0], // 子数组最小乘积
		// 当前遍历到的元素为负，数组最小乘积也为负数，负负相乘等于最大乘积
	}
	ans := dp[0]
	for i := 1; i < n; i++ {
		dp = [2]int{
			max(nums[i], nums[i] * dp[0], nums[i] * dp[1]),
			min(nums[i], nums[i] * dp[0], nums[i] * dp[1]),
		}
		ans = max(ans, dp[0])
	}
 
	return ans
}