152.md

maximum product subarray

解法一

暴力递归求解，当然也可以说是回溯求解。甚至说是深度优先搜索都OK。反正基本上一个意思。

写法是对的，但是超过了时间限制，因为时间复杂度真的太高了，是指数级别的。

func maxProduct(nums []int) int {
    max := -1<<63
    c_maxProduct(nums,&max,1)
    return max
}

func c_maxProduct(nums []int,max *int,cur int){
    // stop 
    if len(nums) == 0 {
        return 
    }
    // process & trill down
    value := nums[0]
    maxT := max
    // Y
    cur *= value
     if *max < cur {
        *max = cur
    }
    c_maxProduct(nums[1:],max,cur)
    // N
    cur = 1
    c_maxProduct(nums[1:],maxT,cur)
    // clear states
}

解法二

动态规划

func maxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
//dp[i][0] 从起始位置到i的最大值
// 最大值在 最大值*num 最小值*num（负数） 和num之间产生。  
//2 3 -2 4
// 
// 初始化
dp := make([][2]int,2)
dp[0]= [2]int{nums[0],nums[0]}
res := nums[0]
// 动态方程的定义和计算
for j := 1;j < len(nums);j++ {
            it,itt := j&1 ,(j-1)&1    
            dp[it][0] = max(dp[itt][0]*nums[j],dp[itt][1]*nums[j],nums[j])
            // 这里的跟nums[j]的比较就是为了寻找是否要舍弃之前的数据，从这里重新开始
            dp[it][1] = min(dp[itt][0]*nums[j],dp[itt][1]*nums[j],nums[j])
            if dp[it][0] > res {
                res = dp[it][0]
            } 
    
    }
    return res
}
func max(x,y,z int)int{
    result := []int{x,y,z}
    sort.Ints(result)
    return result[2]
}
func min(x,y,z int)int{
    result := []int{x,y,z}
    sort.Ints(result)
    return result[0] 
}