maximum-product-subarray.go

// https://leetcode.com/problems/maximum-product-subarray

func maxProduct(nums []int) int {
    numsLen := len(nums)
    
    if numsLen == 0 {
        return 0
    }
    
    if numsLen == 1 {
        return nums[0]
    }
    
    memorized := make([][2]int, numsLen)
    memorized[0] = [2]int{nums[0], nums[0]}
    result := nums[0]
    
    for i := 1; i < numsLen; i++ {
        memorized[i][0] = max(max(memorized[i - 1][0] * nums[i], nums[i]), memorized[i-1][1] * nums[i])
        memorized[i][1] = min(min(memorized[i - 1][1] * nums[i], nums[i]), memorized[i-1][0] * nums[i])
        
        result = max(result, memorized[i][0])
    }
    
    return result
}

func max(a, b int) int {
    if a < b {
        return b
    }
    
    return a
}

func min(a, b int) int {
    if a < b {
        return a
    }
    
    return b
}