前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的152题。
问题描述
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
分析：
正确的解法应该是同时记录最大积和最小积，dp[i][0]表示以nums[i]结尾的子序列的最小积，dp[i][1]表示以nums[i]结尾的子序列的最大积。 初始状态： dp[0][0] = nums[0]; dp[0][1] = nums[0]; 由于可能存在负数，所以有三个数参与判断，状态转移方程： dp[i][0] = min( min(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]), nums[i]) dp[i][1] = max( max(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]), nums[i]) 可以在用一个变量result记录结果，每次计算出最大积时就更新一下result，最后返回result就行，见下面我的代码1，时间复杂度是O(n)O(n)，空间复杂度是O(n)O(n)。
func max_f(a, b int) int {
if a > b {
return a
}
return b
}
func min_f(a, b int) int {
if a < b {
return a
}
return b
}
func maxProduct(nums []int) int {
l := len(nums)
max := nums[0]
maxTemp := max
minTemp := max
var prod1 int
var prod2 int
var temp int
for i := 1; i < l; i++ {
temp = nums[i]
prod1 = temp * maxTemp
prod2 = temp * minTemp
maxTemp = max_f(max_f(prod1,prod2),temp)
minTemp = min_f(min_f(prod1,prod2),temp)
if maxTemp > max {
max = maxTemp
}
//fmt.Println("pos:"+string(pos)+"neg:"+string(neg))
}
return max
}
总结：
这道题并不是很容易。
结语
不管怎么样好好加油。
