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
}
|