Skip to content

Commit 407977f

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0152. Maximum Product Subarray
1 parent 8dfe544 commit 407977f

File tree

9 files changed

+206
-50
lines changed

9 files changed

+206
-50
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -169,11 +169,11 @@
169169
- [跳跃游戏 II](./solution/0000-0099/0045.Jump%20Game%20II/README.md)
170170
- [最大子序和](./solution/0000-0099/0053.Maximum%20Subarray/README.md)
171171
- [环形子数组的最大和](./solution/0900-0999/0918.Maximum%20Sum%20Circular%20Subarray/README.md)
172+
- [乘积最大子序列](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README.md)
172173
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
173174
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
174175
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
175176
- [解码方法](./solution/0000-0099/0091.Decode%20Ways/README.md)
176-
- [乘积最大子序列](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README.md)
177177
- [最长上升子序列](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)
178178
- [俄罗斯套娃信封问题](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README.md)
179179
- [最长公共子序列](./solution/1100-1199/1143.Longest%20Common%20Subsequence/README.md)

‎README_EN.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -163,10 +163,10 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
163163
- [Jump Game II](./solution/0000-0099/0045.Jump%20Game%20II/README_EN.md)
164164
- [Maximum Subarray](./solution/0000-0099/0053.Maximum%20Subarray/README_EN.md)
165165
- [Maximum Sum Circular Subarray](./solution/0900-0999/0918.Maximum%20Sum%20Circular%20Subarray/README_EN.md)
166+
- [Maximum Product Subarray](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README_EN.md)
166167
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
167168
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
168169
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)
169-
- [Maximum Product Subarray](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README_EN.md)
170170
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)
171171
- [Russian Doll Envelopes](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md)
172172
- [Longest Common Subsequence](./solution/1100-1199/1143.Longest%20Common%20Subsequence/README_EN.md)

‎solution/0100-0199/0152.Maximum Product Subarray/README.md

Lines changed: 75 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -48,12 +48,11 @@
4848
```python
4949
class Solution:
5050
def maxProduct(self, nums: List[int]) -> int:
51-
maxf = minf = nums[0]
52-
res, n = nums[0], len(nums)
53-
for i in range(1, n):
54-
p, q = maxf, minf
55-
maxf = max(nums[i], p * nums[i], q * nums[i])
56-
minf = min(nums[i], p * nums[i], q * nums[i])
51+
maxf = minf = res = nums[0]
52+
for num in nums[1:]:
53+
m, n = maxf, minf
54+
maxf = max(num, m * num, n * num)
55+
minf = min(num, m * num, n * num)
5756
res = max(res, maxf)
5857
return res
5958
```
@@ -65,19 +64,83 @@ class Solution:
6564
```java
6665
class Solution {
6766
public int maxProduct(int[] nums) {
68-
int maxf = nums[0], minf = nums[0];
69-
int res = nums[0], n = nums.length;
70-
for (int i = 1; i < n; ++i) {
71-
int p = maxf, q = minf;
72-
maxf = Math.max(nums[i], Math.max(p * nums[i], q * nums[i]));
73-
minf = Math.min(nums[i], Math.min(p * nums[i], q * nums[i]));
67+
int maxf = nums[0], minf = nums[0], res = nums[0];
68+
for (int i = 1; i < nums.length; ++i) {
69+
int m = maxf, n = minf;
70+
maxf = Math.max(nums[i], Math.max(m * nums[i], n * nums[i]));
71+
minf = Math.min(nums[i], Math.min(m * nums[i], n * nums[i]));
7472
res = Math.max(res, maxf);
7573
}
7674
return res;
7775
}
7876
}
7977
```
8078

79+
### **C#**
80+
81+
```cs
82+
public class Solution {
83+
public int MaxProduct(int[] nums) {
84+
int maxf = nums[0], minf = nums[0], res = nums[0];
85+
for (int i = 1; i < nums.Length; ++i)
86+
{
87+
int m = maxf, n = minf;
88+
maxf = Math.Max(nums[i], Math.Max(nums[i] * m, nums[i] * n));
89+
minf = Math.Min(nums[i], Math.Min(nums[i] * m, nums[i] * n));
90+
res = Math.Max(res, maxf);
91+
}
92+
return res;
93+
}
94+
}
95+
```
96+
97+
### **C++**
98+
99+
```cpp
100+
class Solution {
101+
public:
102+
int maxProduct(vector<int>& nums) {
103+
int maxf = nums[0], minf = nums[0], res = nums[0];
104+
for (int i = 1; i < nums.size(); ++i) {
105+
int m = maxf, n = minf;
106+
maxf = max(nums[i], max(nums[i] * m, nums[i] * n));
107+
minf = min(nums[i], min(nums[i] * m, nums[i] * n));
108+
res = max(res, maxf);
109+
}
110+
return res;
111+
}
112+
};
113+
```
114+
115+
### **Go**
116+
117+
```go
118+
func maxProduct(nums []int) int {
119+
maxf, minf, res := nums[0], nums[0], nums[0]
120+
for i := 1; i < len(nums); i++ {
121+
m, n := maxf, minf
122+
maxf = max(nums[i], max(nums[i]*m, nums[i]*n))
123+
minf = min(nums[i], min(nums[i]*m, nums[i]*n))
124+
res = max(res, maxf)
125+
}
126+
return res
127+
}
128+
129+
func max(a, b int) int {
130+
if a > b {
131+
return a
132+
}
133+
return b
134+
}
135+
136+
func min(a, b int) int {
137+
if a < b {
138+
return a
139+
}
140+
return b
141+
}
142+
```
143+
81144
### **...**
82145

83146
```

‎solution/0100-0199/0152.Maximum Product Subarray/README_EN.md

Lines changed: 75 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -46,12 +46,11 @@
4646
```python
4747
class Solution:
4848
def maxProduct(self, nums: List[int]) -> int:
49-
maxf = minf = nums[0]
50-
res, n = nums[0], len(nums)
51-
for i in range(1, n):
52-
p, q = maxf, minf
53-
maxf = max(nums[i], p * nums[i], q * nums[i])
54-
minf = min(nums[i], p * nums[i], q * nums[i])
49+
maxf = minf = res = nums[0]
50+
for num in nums[1:]:
51+
m, n = maxf, minf
52+
maxf = max(num, m * num, n * num)
53+
minf = min(num, m * num, n * num)
5554
res = max(res, maxf)
5655
return res
5756
```
@@ -61,19 +60,83 @@ class Solution:
6160
```java
6261
class Solution {
6362
public int maxProduct(int[] nums) {
64-
int maxf = nums[0], minf = nums[0];
65-
int res = nums[0], n = nums.length;
66-
for (int i = 1; i < n; ++i) {
67-
int p = maxf, q = minf;
68-
maxf = Math.max(nums[i], Math.max(p * nums[i], q * nums[i]));
69-
minf = Math.min(nums[i], Math.min(p * nums[i], q * nums[i]));
63+
int maxf = nums[0], minf = nums[0], res = nums[0];
64+
for (int i = 1; i < nums.length; ++i) {
65+
int m = maxf, n = minf;
66+
maxf = Math.max(nums[i], Math.max(m * nums[i], n * nums[i]));
67+
minf = Math.min(nums[i], Math.min(m * nums[i], n * nums[i]));
7068
res = Math.max(res, maxf);
7169
}
7270
return res;
7371
}
7472
}
7573
```
7674

75+
### **C#**
76+
77+
```cs
78+
public class Solution {
79+
public int MaxProduct(int[] nums) {
80+
int maxf = nums[0], minf = nums[0], res = nums[0];
81+
for (int i = 1; i < nums.Length; ++i)
82+
{
83+
int m = maxf, n = minf;
84+
maxf = Math.Max(nums[i], Math.Max(nums[i] * m, nums[i] * n));
85+
minf = Math.Min(nums[i], Math.Min(nums[i] * m, nums[i] * n));
86+
res = Math.Max(res, maxf);
87+
}
88+
return res;
89+
}
90+
}
91+
```
92+
93+
### **C++**
94+
95+
```cpp
96+
class Solution {
97+
public:
98+
int maxProduct(vector<int>& nums) {
99+
int maxf = nums[0], minf = nums[0], res = nums[0];
100+
for (int i = 1; i < nums.size(); ++i) {
101+
int m = maxf, n = minf;
102+
maxf = max(nums[i], max(nums[i] * m, nums[i] * n));
103+
minf = min(nums[i], min(nums[i] * m, nums[i] * n));
104+
res = max(res, maxf);
105+
}
106+
return res;
107+
}
108+
};
109+
```
110+
111+
### **Go**
112+
113+
```go
114+
func maxProduct(nums []int) int {
115+
maxf, minf, res := nums[0], nums[0], nums[0]
116+
for i := 1; i < len(nums); i++ {
117+
m, n := maxf, minf
118+
maxf = max(nums[i], max(nums[i]*m, nums[i]*n))
119+
minf = min(nums[i], min(nums[i]*m, nums[i]*n))
120+
res = max(res, maxf)
121+
}
122+
return res
123+
}
124+
125+
func max(a, b int) int {
126+
if a > b {
127+
return a
128+
}
129+
return b
130+
}
131+
132+
func min(a, b int) int {
133+
if a < b {
134+
return a
135+
}
136+
return b
137+
}
138+
```
139+
77140
### **...**
78141

79142
```

‎solution/0100-0199/0152.Maximum Product Subarray/Solution.cpp

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
class Solution {
2+
public:
3+
int maxProduct(vector<int>& nums) {
4+
int maxf = nums[0], minf = nums[0], res = nums[0];
5+
for (int i = 1; i < nums.size(); ++i) {
6+
int m = maxf, n = minf;
7+
maxf = max(nums[i], max(nums[i] * m, nums[i] * n));
8+
minf = min(nums[i], min(nums[i] * m, nums[i] * n));
9+
res = max(res, maxf);
10+
}
11+
return res;
12+
}
13+
};

‎solution/0100-0199/0152.Maximum Product Subarray/Solution.cs

Lines changed: 7 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,13 @@
1-
using System;
2-
31
public class Solution {
42
public int MaxProduct(int[] nums) {
5-
var prevMin = 1;
6-
var prevMax = 1;
7-
var result = int.MinValue;
8-
for (var i = 0; i < nums.Length; ++i)
3+
int maxf = nums[0], minf = nums[0], res = nums[0];
4+
for (int i = 1; i < nums.Length; ++i)
95
{
10-
var max = Math.Max(nums[i], Math.Max(nums[i] * prevMin, nums[i] * prevMax));
11-
var min = Math.Min(nums[i], Math.Min(nums[i] * prevMin, nums[i] * prevMax));
12-
result = Math.Max(result, max);
13-
prevMax = max;
14-
prevMin = min;
6+
int m = maxf, n = minf;
7+
maxf = Math.Max(nums[i], Math.Max(nums[i] * m, nums[i] * n));
8+
minf = Math.Min(nums[i], Math.Min(nums[i] * m, nums[i] * n));
9+
res = Math.Max(res, maxf);
1510
}
16-
return result;
11+
return res;
1712
}
1813
}

‎solution/0100-0199/0152.Maximum Product Subarray/Solution.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
func maxProduct(nums []int) int {
2+
maxf, minf, res := nums[0], nums[0], nums[0]
3+
for i := 1; i < len(nums); i++ {
4+
m, n := maxf, minf
5+
maxf = max(nums[i], max(nums[i]*m, nums[i]*n))
6+
minf = min(nums[i], min(nums[i]*m, nums[i]*n))
7+
res = max(res, maxf)
8+
}
9+
return res
10+
}
11+
12+
func max(a, b int) int {
13+
if a > b {
14+
return a
15+
}
16+
return b
17+
}
18+
19+
func min(a, b int) int {
20+
if a < b {
21+
return a
22+
}
23+
return b
24+
}

‎solution/0100-0199/0152.Maximum Product Subarray/Solution.java

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,10 @@
11
class Solution {
22
public int maxProduct(int[] nums) {
3-
int maxf = nums[0], minf = nums[0];
4-
int res = nums[0], n = nums.length;
5-
for (int i = 1; i < n; ++i) {
6-
int p = maxf, q = minf;
7-
maxf = Math.max(nums[i], Math.max(p * nums[i], q * nums[i]));
8-
minf = Math.min(nums[i], Math.min(p * nums[i], q * nums[i]));
3+
int maxf = nums[0], minf = nums[0], res = nums[0];
4+
for (int i = 1; i < nums.length; ++i) {
5+
int m = maxf, n = minf;
6+
maxf = Math.max(nums[i], Math.max(m * nums[i], n * nums[i]));
7+
minf = Math.min(nums[i], Math.min(m * nums[i], n * nums[i]));
98
res = Math.max(res, maxf);
109
}
1110
return res;

‎solution/0100-0199/0152.Maximum Product Subarray/Solution.py

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,9 @@
11
class Solution:
22
def maxProduct(self, nums: List[int]) -> int:
3-
maxf = minf = nums[0]
4-
res, n = nums[0], len(nums)
5-
for i in range(1, n):
6-
p, q = maxf, minf
7-
maxf = max(nums[i], p * nums[i], q * nums[i])
8-
minf = min(nums[i], p * nums[i], q * nums[i])
3+
maxf = minf = res = nums[0]
4+
for num in nums[1:]:
5+
m, n = maxf, minf
6+
maxf = max(num, m * num, n * num)
7+
minf = min(num, m * num, n * num)
98
res = max(res, maxf)
109
return res

0 commit comments

Comments
 (0)