Skip to content

Commit 0fcf785

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1186
No.1186.Maximum Subarray Sum with One Deletion
1 parent 3e933ba commit 0fcf785

File tree

6 files changed

+288
-2
lines changed

6 files changed

+288
-2
lines changed

‎solution/1100-1199/1186.Maximum Subarray Sum with One Deletion/README.md

Lines changed: 103 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,22 +50,124 @@
5050

5151
<!-- 这里可写通用的实现逻辑 -->
5252

53+
**方法一：预处理 + 枚举**
54+
55+
我们可以先预处理出数组 `arr` 以每个元素结尾和开头的最大子数组和，分别存入数组 `left` 和 `right` 中。然后枚举 `arr` 中的每个元素，如果删除该元素，则最大子数组和为 `left[i - 1] + right[i + 1]`。最后取所有可能的最大值即可，注意也可能不删除任何元素。
56+
57+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 `arr` 的长度。
58+
5359
<!-- tabs:start -->
5460

5561
### **Python3**
5662

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

5965
```python
60-
66+
class Solution:
67+
def maximumSum(self, arr: List[int]) -> int:
68+
n = len(arr)
69+
left = [0] * n
70+
right = [0] * n
71+
t = 0
72+
for i, v in enumerate(arr):
73+
t = max(t, 0) + v
74+
left[i] = t
75+
t = 0
76+
for i in range(n - 1, -1, -1):
77+
t = max(t, 0) + arr[i]
78+
right[i] = t
79+
ans = max(left)
80+
for i in range(1, n - 1):
81+
ans = max(ans, left[i - 1] + right[i + 1])
82+
return ans
6183
```
6284

6385
### **Java**
6486

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

6789
```java
90+
class Solution {
91+
public int maximumSum(int[] arr) {
92+
int n = arr.length;
93+
int[] left = new int[n];
94+
int[] right = new int[n];
95+
int t = 0;
96+
for (int i = 0; i < n; ++i) {
97+
t = Math.max(t, 0) + arr[i];
98+
left[i] = t;
99+
}
100+
t = 0;
101+
for (int i = n - 1; i >= 0; --i) {
102+
t = Math.max(t, 0) + arr[i];
103+
right[i] = t;
104+
}
105+
int ans = Arrays.stream(left).max().getAsInt();
106+
for (int i = 1; i < n - 1; ++i) {
107+
ans = Math.max(ans, left[i - 1] + right[i + 1]);
108+
}
109+
return ans;
110+
}
111+
}
112+
```
113+
114+
### **C++**
115+
116+
```cpp
117+
class Solution {
118+
public:
119+
int maximumSum(vector<int>& arr) {
120+
int n = arr.size();
121+
int left[n];
122+
int right[n];
123+
for (int i = 0, t = 0; i < n; ++i) {
124+
t = max(t, 0) + arr[i];
125+
left[i] = t;
126+
}
127+
for (int i = n - 1, t = 0; ~i; --i) {
128+
t = max(t, 0) + arr[i];
129+
right[i] = t;
130+
}
131+
int ans = *max_element(left, left + n);
132+
for (int i = 1; i < n - 1; ++i) {
133+
ans = max(ans, left[i - 1] + right[i + 1]);
134+
}
135+
return ans;
136+
}
137+
};
138+
```
68139
140+
### **Go**
141+
142+
```go
143+
func maximumSum(arr []int) int {
144+
n := len(arr)
145+
left := make([]int, n)
146+
right := make([]int, n)
147+
t := 0
148+
ans := math.MinInt32
149+
for i, v := range arr {
150+
t = max(t, 0) + v
151+
left[i] = t
152+
ans = max(ans, left[i])
153+
}
154+
t = 0
155+
for i := n - 1; i >= 0; i-- {
156+
t = max(t, 0) + arr[i]
157+
right[i] = t
158+
}
159+
for i := 1; i < n-1; i++ {
160+
ans = max(ans, left[i-1]+right[i+1])
161+
}
162+
return ans
163+
}
164+
165+
func max(a, b int) int {
166+
if a > b {
167+
return a
168+
}
169+
return b
170+
}
69171
```
70172

71173
### **...**

‎solution/1100-1199/1186.Maximum Subarray Sum with One Deletion/README_EN.md

Lines changed: 97 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -47,13 +47,109 @@
4747
### **Python3**
4848

4949
```python
50-
50+
class Solution:
51+
def maximumSum(self, arr: List[int]) -> int:
52+
n = len(arr)
53+
left = [0] * n
54+
right = [0] * n
55+
t = 0
56+
for i, v in enumerate(arr):
57+
t = max(t, 0) + v
58+
left[i] = t
59+
t = 0
60+
for i in range(n - 1, -1, -1):
61+
t = max(t, 0) + arr[i]
62+
right[i] = t
63+
ans = max(left)
64+
for i in range(1, n - 1):
65+
ans = max(ans, left[i - 1] + right[i + 1])
66+
return ans
5167
```
5268

5369
### **Java**
5470

5571
```java
72+
class Solution {
73+
public int maximumSum(int[] arr) {
74+
int n = arr.length;
75+
int[] left = new int[n];
76+
int[] right = new int[n];
77+
int t = 0;
78+
for (int i = 0; i < n; ++i) {
79+
t = Math.max(t, 0) + arr[i];
80+
left[i] = t;
81+
}
82+
t = 0;
83+
for (int i = n - 1; i >= 0; --i) {
84+
t = Math.max(t, 0) + arr[i];
85+
right[i] = t;
86+
}
87+
int ans = Arrays.stream(left).max().getAsInt();
88+
for (int i = 1; i < n - 1; ++i) {
89+
ans = Math.max(ans, left[i - 1] + right[i + 1]);
90+
}
91+
return ans;
92+
}
93+
}
94+
```
95+
96+
### **C++**
97+
98+
```cpp
99+
class Solution {
100+
public:
101+
int maximumSum(vector<int>& arr) {
102+
int n = arr.size();
103+
int left[n];
104+
int right[n];
105+
for (int i = 0, t = 0; i < n; ++i) {
106+
t = max(t, 0) + arr[i];
107+
left[i] = t;
108+
}
109+
for (int i = n - 1, t = 0; ~i; --i) {
110+
t = max(t, 0) + arr[i];
111+
right[i] = t;
112+
}
113+
int ans = *max_element(left, left + n);
114+
for (int i = 1; i < n - 1; ++i) {
115+
ans = max(ans, left[i - 1] + right[i + 1]);
116+
}
117+
return ans;
118+
}
119+
};
120+
```
56121
122+
### **Go**
123+
124+
```go
125+
func maximumSum(arr []int) int {
126+
n := len(arr)
127+
left := make([]int, n)
128+
right := make([]int, n)
129+
t := 0
130+
ans := math.MinInt32
131+
for i, v := range arr {
132+
t = max(t, 0) + v
133+
left[i] = t
134+
ans = max(ans, left[i])
135+
}
136+
t = 0
137+
for i := n - 1; i >= 0; i-- {
138+
t = max(t, 0) + arr[i]
139+
right[i] = t
140+
}
141+
for i := 1; i < n-1; i++ {
142+
ans = max(ans, left[i-1]+right[i+1])
143+
}
144+
return ans
145+
}
146+
147+
func max(a, b int) int {
148+
if a > b {
149+
return a
150+
}
151+
return b
152+
}
57153
```
58154

59155
### **...**

‎solution/1100-1199/1186.Maximum Subarray Sum with One Deletion/Solution.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public:
3+
int maximumSum(vector<int>& arr) {
4+
int n = arr.size();
5+
int left[n];
6+
int right[n];
7+
for (int i = 0, t = 0; i < n; ++i) {
8+
t = max(t, 0) + arr[i];
9+
left[i] = t;
10+
}
11+
for (int i = n - 1, t = 0; ~i; --i) {
12+
t = max(t, 0) + arr[i];
13+
right[i] = t;
14+
}
15+
int ans = *max_element(left, left + n);
16+
for (int i = 1; i < n - 1; ++i) {
17+
ans = max(ans, left[i - 1] + right[i + 1]);
18+
}
19+
return ans;
20+
}
21+
};

‎solution/1100-1199/1186.Maximum Subarray Sum with One Deletion/Solution.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
func maximumSum(arr []int) int {
2+
n := len(arr)
3+
left := make([]int, n)
4+
right := make([]int, n)
5+
t := 0
6+
ans := math.MinInt32
7+
for i, v := range arr {
8+
t = max(t, 0) + v
9+
left[i] = t
10+
ans = max(ans, left[i])
11+
}
12+
t = 0
13+
for i := n - 1; i >= 0; i-- {
14+
t = max(t, 0) + arr[i]
15+
right[i] = t
16+
}
17+
for i := 1; i < n-1; i++ {
18+
ans = max(ans, left[i-1]+right[i+1])
19+
}
20+
return ans
21+
}
22+
23+
func max(a, b int) int {
24+
if a > b {
25+
return a
26+
}
27+
return b
28+
}

‎solution/1100-1199/1186.Maximum Subarray Sum with One Deletion/Solution.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
class Solution {
2+
public int maximumSum(int[] arr) {
3+
int n = arr.length;
4+
int[] left = new int[n];
5+
int[] right = new int[n];
6+
int t = 0;
7+
for (int i = 0; i < n; ++i) {
8+
t = Math.max(t, 0) + arr[i];
9+
left[i] = t;
10+
}
11+
t = 0;
12+
for (int i = n - 1; i >= 0; --i) {
13+
t = Math.max(t, 0) + arr[i];
14+
right[i] = t;
15+
}
16+
int ans = Arrays.stream(left).max().getAsInt();
17+
for (int i = 1; i < n - 1; ++i) {
18+
ans = Math.max(ans, left[i - 1] + right[i + 1]);
19+
}
20+
return ans;
21+
}
22+
}

‎solution/1100-1199/1186.Maximum Subarray Sum with One Deletion/Solution.py

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class Solution:
2+
def maximumSum(self, arr: List[int]) -> int:
3+
n = len(arr)
4+
left = [0] * n
5+
right = [0] * n
6+
t = 0
7+
for i, v in enumerate(arr):
8+
t = max(t, 0) + v
9+
left[i] = t
10+
t = 0
11+
for i in range(n - 1, -1, -1):
12+
t = max(t, 0) + arr[i]
13+
right[i] = t
14+
ans = max(left)
15+
for i in range(1, n - 1):
16+
ans = max(ans, left[i - 1] + right[i + 1])
17+
return ans

0 commit comments

Comments
 (0)