-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
918.py
80 lines (65 loc) · 2.11 KB
/
918.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
__________________________________________________________________________________________________
sample 468 ms submission
from typing import List
# leetcode.com boilerplate
class Solution:
def maxSubarraySumCircular(self, A: List[int]) -> int:
max_sum = max_subarray_sum(A)
if max_sum > 0:
return max(max_sum, sum(A) - min_subarray_sum(A))
else:
return max_sum
def max_subarray_sum(numbers):
assert len(numbers) > 0
max_so_far = numbers[0]
max_to_me = max(numbers[0], 0)
for value in numbers[1:]:
max_to_me += value
if max_to_me > max_so_far:
max_so_far = max_to_me
if max_to_me < 0:
max_to_me = 0
return max_so_far
def min_subarray_sum(numbers):
assert len(numbers) > 0
min_so_far = numbers[0]
min_to_me = min(numbers[0], 0)
for value in numbers[1:]:
min_to_me += value
if min_to_me < min_so_far:
min_so_far = min_to_me
if min_to_me > 0:
min_to_me = 0
return min_so_far
__________________________________________________________________________________________________
sample 484 ms submission
class Solution:
def maxSubarraySumCircular(self, A: List[int]) -> int:
sub_max=[]
sub_min=[]
cur_max=0
cur_min=0
for i in A:
if i>0:
cur_max+=i
sub_min.append(cur_min)
if i+cur_min>=0:
cur_min=0
else:
cur_min+=i
elif i<0:
cur_min+=i
sub_max.append(cur_max)
if i+cur_max<=0:
cur_max=0
else:
cur_max+=i
if len(sub_max)==len(A):
return max(A)
if len(sub_min)==len(A):
return sum(A)
sub_min.append(cur_min)
sub_max.append(cur_max)
s=sum(A)
return max(max(sub_max),s-min(sub_min))
__________________________________________________________________________________________________