1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def maximumSum(self, a: List[int]) -> int:
n = len(a)
maxEndHere = [0] * n
maxStartHere = [0] * n
max_sum = a[0]
maxEndHere[0] = a[0]
for i in range(1, n):
maxEndHere[i] = max(a[i], maxEndHere[i - 1] + a[i])
max_sum = max(max_sum, maxEndHere[i])
maxStartHere[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
maxStartHere[i] = max(a[i], maxStartHere[i + 1] + a[i])
for i in range(1, n - 1):
max_sum = max(max_sum, maxEndHere[i - 1] + maxStartHere[i + 1])
return max_sum
|