1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

// @Title: 乘积最大子数组 (Maximum Product Subarray)
// @Author: 15816537946@163.com
// @Date: 2019-10-17 13:57:27
// @Runtime: 4 ms
// @Memory: 2.6 MB
/*
 * @lc app=leetcode.cn id=152 lang=golang
 *
 * [152] 乘积最大子序列
 *
 * https://leetcode-cn.com/problems/maximum-product-subarray/description/
 *
 * algorithms
 * Medium (35.12%)
 * Likes:    237
 * Dislikes: 0
 * Total Accepted:    16.8K
 * Total Submissions: 47.7K
 * Testcase Example:  '[2,3,-2,4]'
 *
 * 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
 *
 * 示例 1:
 *
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 *
 *
 * 示例 2:
 *
 * 输入: [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 *
 */

func maxProduct(nums []int) int {
	if len(nums) < 1 {
		return 0
	}

	lastMin, lastMax := 1, 1
	sum := nums[0]

	for i := 0; i < len(nums); i++ {
		if nums[i] < 0 {
			lastMax, lastMin = lastMin, lastMax
		}

		lastMax = max(lastMax*nums[i], nums[i])
		lastMin = min(lastMin*nums[i], nums[i])

		if sum < lastMax {
			sum = lastMax
		}
	}

	return sum
}

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

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