Skip to content

Commit 535ff81

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1567. Maximum Length of Subarray With Positive Product
1 parent 48cb588 commit 535ff81

File tree

8 files changed

+339
-24
lines changed

8 files changed

+339
-24
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -170,6 +170,7 @@
170170
- [最大子序和](./solution/0000-0099/0053.Maximum%20Subarray/README.md)
171171
- [环形子数组的最大和](./solution/0900-0999/0918.Maximum%20Sum%20Circular%20Subarray/README.md)
172172
- [乘积最大子序列](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README.md)
173+
- [乘积为正数的最长子数组长度](./solution/1500-1599/1567.Maximum%20Length%20of%20Subarray%20With%20Positive%20Product/README.md)
173174
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
174175
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
175176
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
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)
166166
- [Maximum Product Subarray](./solution/0100-0199/0152.Maximum%20Product%20Subarray/README_EN.md)
167+
- [Maximum Length of Subarray With Positive Product](./solution/1500-1599/1567.Maximum%20Length%20of%20Subarray%20With%20Positive%20Product/README_EN.md)
167168
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
168169
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
169170
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)

‎solution/1500-1599/1567.Maximum Length of Subarray With Positive Product/README.md

Lines changed: 118 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -68,15 +68,132 @@
6868
<!-- 这里可写当前语言的特殊实现逻辑 -->
6969

7070
```python
71-
71+
class Solution:
72+
def getMaxLen(self, nums: List[int]) -> int:
73+
f1 = 1 if nums[0] > 0 else 0
74+
f2 = 1 if nums[0] < 0 else 0
75+
res = f1
76+
for num in nums[1:]:
77+
pf1, pf2 = f1, f2
78+
if num > 0:
79+
f1 += 1
80+
if f2 > 0:
81+
f2 += 1
82+
else:
83+
f2 = 0
84+
elif num < 0:
85+
pf1, pf2 = f1, f2
86+
f2 = pf1 + 1
87+
if pf2 > 0:
88+
f1 = pf2 + 1
89+
else:
90+
f1 = 0
91+
else:
92+
f1 = 0
93+
f2 = 0
94+
res = max(res, f1)
95+
return res
7296
```
7397

7498
### **Java**
7599

76100
<!-- 这里可写当前语言的特殊实现逻辑 -->
77101

78102
```java
103+
class Solution {
104+
public int getMaxLen(int[] nums) {
105+
int f1 = nums[0] > 0 ? 1 : 0;
106+
int f2 = nums[0] < 0 ? 1 : 0;
107+
int res = f1;
108+
for (int i = 1; i < nums.length; ++i) {
109+
if (nums[i] > 0) {
110+
++f1;
111+
f2 = f2 > 0 ? f2 + 1 : 0;
112+
} else if (nums[i] < 0) {
113+
int pf1 = f1, pf2 = f2;
114+
f2 = pf1 + 1;
115+
f1 = pf2 > 0 ? pf2 + 1 : 0;
116+
} else {
117+
f1 = 0;
118+
f2 = 0;
119+
}
120+
res = Math.max(res, f1);
121+
}
122+
return res;
123+
}
124+
}
125+
```
126+
127+
### **C++**
128+
129+
```cpp
130+
class Solution {
131+
public:
132+
int getMaxLen(vector<int>& nums) {
133+
int f1 = nums[0] > 0 ? 1 : 0;
134+
int f2 = nums[0] < 0 ? 1 : 0;
135+
int res = f1;
136+
for (int i = 1; i < nums.size(); ++i) {
137+
if (nums[i] > 0) {
138+
++f1;
139+
f2 = f2 > 0 ? f2 + 1 : 0;
140+
} else if (nums[i] < 0) {
141+
int pf1 = f1, pf2 = f2;
142+
f2 = pf1 + 1;
143+
f1 = pf2 > 0 ? pf2 + 1 : 0;
144+
} else {
145+
f1 = 0;
146+
f2 = 0;
147+
}
148+
res = max(res, f1);
149+
}
150+
return res;
151+
}
152+
};
153+
```
79154
155+
### **Go**
156+
157+
```go
158+
func getMaxLen(nums []int) int {
159+
f1, f2 := 0, 0
160+
if nums[0] > 0 {
161+
f1 = 1
162+
}
163+
if nums[0] < 0 {
164+
f2 = 1
165+
}
166+
res := f1
167+
for i := 1; i < len(nums); i++ {
168+
if nums[i] > 0 {
169+
f1++
170+
if f2 > 0 {
171+
f2++
172+
} else {
173+
f2 = 0
174+
}
175+
} else if nums[i] < 0 {
176+
pf1, pf2 := f1, f2
177+
f2 = pf1 + 1
178+
if pf2 > 0 {
179+
f1 = pf2 + 1
180+
} else {
181+
f1 = 0
182+
}
183+
} else {
184+
f1, f2 = 0, 0
185+
}
186+
res = max(res, f1)
187+
}
188+
return res
189+
}
190+
191+
func max(a, b int) int {
192+
if a > b {
193+
return a
194+
}
195+
return b
196+
}
80197
```
81198

82199
### **...**

‎solution/1500-1599/1567.Maximum Length of Subarray With Positive Product/README_EN.md

Lines changed: 118 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,13 +65,130 @@ Notice that we cannot include 0 in the subarray since that&#39;ll make the produ
6565
### **Python3**
6666

6767
```python
68-
68+
class Solution:
69+
def getMaxLen(self, nums: List[int]) -> int:
70+
f1 = 1 if nums[0] > 0 else 0
71+
f2 = 1 if nums[0] < 0 else 0
72+
res = f1
73+
for num in nums[1:]:
74+
pf1, pf2 = f1, f2
75+
if num > 0:
76+
f1 += 1
77+
if f2 > 0:
78+
f2 += 1
79+
else:
80+
f2 = 0
81+
elif num < 0:
82+
pf1, pf2 = f1, f2
83+
f2 = pf1 + 1
84+
if pf2 > 0:
85+
f1 = pf2 + 1
86+
else:
87+
f1 = 0
88+
else:
89+
f1 = 0
90+
f2 = 0
91+
res = max(res, f1)
92+
return res
6993
```
7094

7195
### **Java**
7296

7397
```java
98+
class Solution {
99+
public int getMaxLen(int[] nums) {
100+
int f1 = nums[0] > 0 ? 1 : 0;
101+
int f2 = nums[0] < 0 ? 1 : 0;
102+
int res = f1;
103+
for (int i = 1; i < nums.length; ++i) {
104+
if (nums[i] > 0) {
105+
++f1;
106+
f2 = f2 > 0 ? f2 + 1 : 0;
107+
} else if (nums[i] < 0) {
108+
int pf1 = f1, pf2 = f2;
109+
f2 = pf1 + 1;
110+
f1 = pf2 > 0 ? pf2 + 1 : 0;
111+
} else {
112+
f1 = 0;
113+
f2 = 0;
114+
}
115+
res = Math.max(res, f1);
116+
}
117+
return res;
118+
}
119+
}
120+
```
121+
122+
### **C++**
123+
124+
```cpp
125+
class Solution {
126+
public:
127+
int getMaxLen(vector<int>& nums) {
128+
int f1 = nums[0] > 0 ? 1 : 0;
129+
int f2 = nums[0] < 0 ? 1 : 0;
130+
int res = f1;
131+
for (int i = 1; i < nums.size(); ++i) {
132+
if (nums[i] > 0) {
133+
++f1;
134+
f2 = f2 > 0 ? f2 + 1 : 0;
135+
} else if (nums[i] < 0) {
136+
int pf1 = f1, pf2 = f2;
137+
f2 = pf1 + 1;
138+
f1 = pf2 > 0 ? pf2 + 1 : 0;
139+
} else {
140+
f1 = 0;
141+
f2 = 0;
142+
}
143+
res = max(res, f1);
144+
}
145+
return res;
146+
}
147+
};
148+
```
74149
150+
### **Go**
151+
152+
```go
153+
func getMaxLen(nums []int) int {
154+
f1, f2 := 0, 0
155+
if nums[0] > 0 {
156+
f1 = 1
157+
}
158+
if nums[0] < 0 {
159+
f2 = 1
160+
}
161+
res := f1
162+
for i := 1; i < len(nums); i++ {
163+
if nums[i] > 0 {
164+
f1++
165+
if f2 > 0 {
166+
f2++
167+
} else {
168+
f2 = 0
169+
}
170+
} else if nums[i] < 0 {
171+
pf1, pf2 := f1, f2
172+
f2 = pf1 + 1
173+
if pf2 > 0 {
174+
f1 = pf2 + 1
175+
} else {
176+
f1 = 0
177+
}
178+
} else {
179+
f1, f2 = 0, 0
180+
}
181+
res = max(res, f1)
182+
}
183+
return res
184+
}
185+
186+
func max(a, b int) int {
187+
if a > b {
188+
return a
189+
}
190+
return b
191+
}
75192
```
76193

77194
### **...**

‎solution/1500-1599/1567.Maximum Length of Subarray With Positive Product/Solution.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution {
2+
public:
3+
int getMaxLen(vector<int>& nums) {
4+
int f1 = nums[0] > 0 ? 1 : 0;
5+
int f2 = nums[0] < 0 ? 1 : 0;
6+
int res = f1;
7+
for (int i = 1; i < nums.size(); ++i) {
8+
if (nums[i] > 0) {
9+
++f1;
10+
f2 = f2 > 0 ? f2 + 1 : 0;
11+
} else if (nums[i] < 0) {
12+
int pf1 = f1, pf2 = f2;
13+
f2 = pf1 + 1;
14+
f1 = pf2 > 0 ? pf2 + 1 : 0;
15+
} else {
16+
f1 = 0;
17+
f2 = 0;
18+
}
19+
res = max(res, f1);
20+
}
21+
return res;
22+
}
23+
};

‎solution/1500-1599/1567.Maximum Length of Subarray With Positive Product/Solution.go

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
func getMaxLen(nums []int) int {
2+
f1, f2 := 0, 0
3+
if nums[0] > 0 {
4+
f1 = 1
5+
}
6+
if nums[0] < 0 {
7+
f2 = 1
8+
}
9+
res := f1
10+
for i := 1; i < len(nums); i++ {
11+
if nums[i] > 0 {
12+
f1++
13+
if f2 > 0 {
14+
f2++
15+
} else {
16+
f2 = 0
17+
}
18+
} else if nums[i] < 0 {
19+
pf1, pf2 := f1, f2
20+
f2 = pf1 + 1
21+
if pf2 > 0 {
22+
f1 = pf2 + 1
23+
} else {
24+
f1 = 0
25+
}
26+
} else {
27+
f1, f2 = 0, 0
28+
}
29+
res = max(res, f1)
30+
}
31+
return res
32+
}
33+
34+
func max(a, b int) int {
35+
if a > b {
36+
return a
37+
}
38+
return b
39+
}

‎solution/1500-1599/1567.Maximum Length of Subarray With Positive Product/Solution.java

Lines changed: 14 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,21 @@
11
class Solution {
2-
public int getMaxLen(int[] nums) {
3-
// p[i] = n[i-1] + 1, nums[i] < 0
4-
// p[i] = p[i-1] + 1, nums[i] > 0
5-
// p[i] = 0, nums[i] = 0
6-
7-
// n[i] = p[i-1] + 1, nums[i] < 0
8-
// n[i] = n[i-1] + 1, nums[i] > 0
9-
// n[i] = 0, nums[i] = 0
10-
int[] p = new int[nums.length];
11-
int[] n = new int[nums.length];
12-
p[0] = nums[0] > 0 ? 1 : 0;
13-
n[0] = nums[0] < 0 ? 1 : 0;
14-
int res = Math.max(p[0], 0);
15-
for (int i = 1; i < nums.length; i++) {
2+
public int getMaxLen(int[] nums) {
3+
int f1 = nums[0] > 0 ? 1 : 0;
4+
int f2 = nums[0] < 0 ? 1 : 0;
5+
int res = f1;
6+
for (int i = 1; i < nums.length; ++i) {
167
if (nums[i] > 0) {
17-
p[i] = p[i - 1] + 1;
18-
n[i] = n[i - 1] == 0 ? 0 : n[i - 1] + 1;
19-
} else if (nums[i] == 0) {
20-
p[i] = 0;
21-
n[i] = 0;
8+
++f1;
9+
f2 = f2 > 0 ? f2 + 1 : 0;
10+
} else if (nums[i] < 0) {
11+
int pf1 = f1, pf2 = f2;
12+
f2 = pf1 + 1;
13+
f1 = pf2 > 0 ? pf2 + 1 : 0;
2214
} else {
23-
p[i] = n[i - 1] == 0 ? 0 : n[i - 1] + 1;
24-
n[i] = p[i - 1] + 1;
15+
f1 = 0;
16+
f2 = 0;
2517
}
26-
res = Math.max(res, p[i]);
18+
res = Math.max(res, f1);
2719
}
2820
return res;
2921
}

0 commit comments

Comments
 (0)