Skip to content

Commit 913a54b

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0918. Maximum Sum Circular Subaray
1 parent 6d6f012 commit 913a54b

File tree

8 files changed

+217
-17
lines changed

8 files changed

+217
-17
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -168,6 +168,7 @@
168168
- [跳跃游戏](./solution/0000-0099/0055.Jump%20Game/README.md)
169169
- [跳跃游戏 II](./solution/0000-0099/0045.Jump%20Game%20II/README.md)
170170
- [最大子序和](./solution/0000-0099/0053.Maximum%20Subarray/README.md)
171+
- [环形子数组的最大和](./solution/0900-0999/0918.Maximum%20Sum%20Circular%20Subarray/README.md)
171172
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
172173
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
173174
- [最小路径和](./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
@@ -162,6 +162,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
162162
- [Jump Game](./solution/0000-0099/0055.Jump%20Game/README_EN.md)
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)
165+
- [Maximum Sum Circular Subarray](./solution/0900-0999/0918.Maximum%20Sum%20Circular%20Subarray/README_EN.md)
165166
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
166167
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
167168
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)

‎solution/0900-0999/0918.Maximum Sum Circular Subarray/README.md

Lines changed: 81 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -58,27 +58,106 @@
5858
<li><code>1 &lt;= A.length &lt;= 30000</code></li>
5959
</ol>
6060

61-
6261
## 解法
6362

6463
<!-- 这里可写通用的实现逻辑 -->
6564

65+
环形子数组的最大和，可分为两种情况：无环最大和、有环最大和。求其较大值即可。
66+
67+
无环最大和 s1 的求解可参考：[53. 最大子序和](/solution/0000-0099/0053.Maximum%20Subarray/README.md)。
68+
69+
对于有环最大和，我们可以转换为求最小子序和 s2，然后用 sum 减去最小子序和，得到有环的最大和。
70+
71+
注意：若数组所有元素均不大于 0，直接返回无环最大和 s1 即可。
72+
6673
<!-- tabs:start -->
6774

6875
### **Python3**
6976

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

7279
```python
73-
80+
class Solution:
81+
def maxSubarraySumCircular(self, nums: List[int]) -> int:
82+
s1 = s2 = f1 = f2 = nums[0]
83+
for num in nums[1:]:
84+
f1 = num + max(f1, 0)
85+
f2 = num + min(f2, 0)
86+
s1 = max(s1, f1)
87+
s2 = min(s2, f2)
88+
return s1 if s1 <= 0 else max(s1, sum(nums) - s2)
7489
```
7590

7691
### **Java**
7792

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

8095
```java
96+
class Solution {
97+
public int maxSubarraySumCircular(int[] nums) {
98+
int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
99+
for (int i = 1; i < nums.length; ++i) {
100+
total += nums[i];
101+
f1 = nums[i] + Math.max(f1, 0);
102+
f2 = nums[i] + Math.min(f2, 0);
103+
s1 = Math.max(s1, f1);
104+
s2 = Math.min(s2, f2);
105+
}
106+
return s1 > 0 ? Math.max(s1, total - s2) : s1;
107+
}
108+
}
109+
```
110+
111+
### **C++**
112+
113+
```cpp
114+
class Solution {
115+
public:
116+
int maxSubarraySumCircular(vector<int>& nums) {
117+
int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
118+
for (int i = 1; i < nums.size(); ++i) {
119+
total += nums[i];
120+
f1 = nums[i] + max(f1, 0);
121+
f2 = nums[i] + min(f2, 0);
122+
s1 = max(s1, f1);
123+
s2 = min(s2, f2);
124+
}
125+
return s1 > 0 ? max(s1, total - s2) : s1;
126+
}
127+
};
128+
```
81129
130+
### **Go**
131+
132+
```go
133+
func maxSubarraySumCircular(nums []int) int {
134+
s1, s2, f1, f2, total := nums[0], nums[0], nums[0], nums[0], nums[0]
135+
for i := 1; i < len(nums); i++ {
136+
total += nums[i]
137+
f1 = nums[i] + max(f1, 0)
138+
f2 = nums[i] + min(f2, 0)
139+
s1 = max(s1, f1)
140+
s2 = min(s2, f2)
141+
}
142+
if s1 <= 0 {
143+
return s1
144+
}
145+
return max(s1, total-s2)
146+
}
147+
148+
func max(a, b int) int {
149+
if a > b {
150+
return a
151+
}
152+
return b
153+
}
154+
155+
func min(a, b int) int {
156+
if a < b {
157+
return a
158+
}
159+
return b
160+
}
82161
```
83162

84163
### **...**

‎solution/0900-0999/0918.Maximum Sum Circular Subarray/README_EN.md

Lines changed: 73 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -138,13 +138,85 @@
138138
### **Python3**
139139

140140
```python
141-
141+
class Solution:
142+
def maxSubarraySumCircular(self, nums: List[int]) -> int:
143+
s1 = s2 = f1 = f2 = nums[0]
144+
for num in nums[1:]:
145+
f1 = num + max(f1, 0)
146+
f2 = num + min(f2, 0)
147+
s1 = max(s1, f1)
148+
s2 = min(s2, f2)
149+
return s1 if s1 <= 0 else max(s1, sum(nums) - s2)
142150
```
143151

144152
### **Java**
145153

146154
```java
155+
class Solution {
156+
public int maxSubarraySumCircular(int[] nums) {
157+
int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
158+
for (int i = 1; i < nums.length; ++i) {
159+
total += nums[i];
160+
f1 = nums[i] + Math.max(f1, 0);
161+
f2 = nums[i] + Math.min(f2, 0);
162+
s1 = Math.max(s1, f1);
163+
s2 = Math.min(s2, f2);
164+
}
165+
return s1 > 0 ? Math.max(s1, total - s2) : s1;
166+
}
167+
}
168+
```
169+
170+
### **C++**
171+
172+
```cpp
173+
class Solution {
174+
public:
175+
int maxSubarraySumCircular(vector<int>& nums) {
176+
int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
177+
for (int i = 1; i < nums.size(); ++i) {
178+
total += nums[i];
179+
f1 = nums[i] + max(f1, 0);
180+
f2 = nums[i] + min(f2, 0);
181+
s1 = max(s1, f1);
182+
s2 = min(s2, f2);
183+
}
184+
return s1 > 0 ? max(s1, total - s2) : s1;
185+
}
186+
};
187+
```
147188
189+
### **Go**
190+
191+
```go
192+
func maxSubarraySumCircular(nums []int) int {
193+
s1, s2, f1, f2, total := nums[0], nums[0], nums[0], nums[0], nums[0]
194+
for i := 1; i < len(nums); i++ {
195+
total += nums[i]
196+
f1 = nums[i] + max(f1, 0)
197+
f2 = nums[i] + min(f2, 0)
198+
s1 = max(s1, f1)
199+
s2 = min(s2, f2)
200+
}
201+
if s1 <= 0 {
202+
return s1
203+
}
204+
return max(s1, total-s2)
205+
}
206+
207+
func max(a, b int) int {
208+
if a > b {
209+
return a
210+
}
211+
return b
212+
}
213+
214+
func min(a, b int) int {
215+
if a < b {
216+
return a
217+
}
218+
return b
219+
}
148220
```
149221

150222
### **...**

‎solution/0900-0999/0918.Maximum Sum Circular Subarray/Solution.cpp

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
class Solution {
2+
public:
3+
int maxSubarraySumCircular(vector<int>& nums) {
4+
int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
5+
for (int i = 1; i < nums.size(); ++i) {
6+
total += nums[i];
7+
f1 = nums[i] + max(f1, 0);
8+
f2 = nums[i] + min(f2, 0);
9+
s1 = max(s1, f1);
10+
s2 = min(s2, f2);
11+
}
12+
return s1 > 0 ? max(s1, total - s2) : s1;
13+
}
14+
};

‎solution/0900-0999/0918.Maximum Sum Circular Subarray/Solution.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
func maxSubarraySumCircular(nums []int) int {
2+
s1, s2, f1, f2, total := nums[0], nums[0], nums[0], nums[0], nums[0]
3+
for i := 1; i < len(nums); i++ {
4+
total += nums[i]
5+
f1 = nums[i] + max(f1, 0)
6+
f2 = nums[i] + min(f2, 0)
7+
s1 = max(s1, f1)
8+
s2 = min(s2, f2)
9+
}
10+
if s1 <= 0 {
11+
return s1
12+
}
13+
return max(s1, total-s2)
14+
}
15+
16+
func max(a, b int) int {
17+
if a > b {
18+
return a
19+
}
20+
return b
21+
}
22+
23+
func min(a, b int) int {
24+
if a < b {
25+
return a
26+
}
27+
return b
28+
}

‎solution/0900-0999/0918.Maximum Sum Circular Subarray/Solution.java

Lines changed: 10 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,13 @@
11
class Solution {
2-
public int maxSubarraySumCircular(int[] A) {
3-
int tot = 0;
4-
int curMax = 0;
5-
int maxSum = Integer.MIN_VALUE;
6-
int curMin = 0;
7-
int minSum = Integer.MAX_VALUE;
8-
for (int x : A) {
9-
tot += x;
10-
curMax = Math.max(curMax + x, x);
11-
maxSum = Math.max(maxSum, curMax);
12-
curMin = Math.min(curMin + x, x);
13-
minSum = Math.min(minSum, curMin);
2+
public int maxSubarraySumCircular(int[] nums) {
3+
int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
4+
for (int i = 1; i < nums.length; ++i) {
5+
total += nums[i];
6+
f1 = nums[i] + Math.max(f1, 0);
7+
f2 = nums[i] + Math.min(f2, 0);
8+
s1 = Math.max(s1, f1);
9+
s2 = Math.min(s2, f2);
1410
}
15-
return maxSum > 0 ? Math.max(maxSum, tot - minSum) : maxSum;
11+
return s1 > 0 ? Math.max(s1, total - s2) : s1;
1612
}
17-
}
13+
}

‎solution/0900-0999/0918.Maximum Sum Circular Subarray/Solution.py

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
class Solution:
2+
def maxSubarraySumCircular(self, nums: List[int]) -> int:
3+
s1 = s2 = f1 = f2 = nums[0]
4+
for num in nums[1:]:
5+
f1 = num + max(f1, 0)
6+
f2 = num + min(f2, 0)
7+
s1 = max(s1, f1)
8+
s2 = min(s2, f2)
9+
return s1 if s1 <= 0 else max(s1, sum(nums) - s2)

0 commit comments

Comments
 (0)