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
|
# 53. Maximum Subarray
"""
given an integer array 'nums', find the subarray with the largest sum, and
return its sum.
"""
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_sum, curr_sum = float("-inf"), 0
for i in nums:
curr_sum += i
if max_sum < curr_sum:
max_sum = curr_sum
if curr_sum < 0:
curr_sum = 0
return max_sum
if __name__ == "__main__":
obj = Solution()
print(obj.maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(obj.maxSubArray(nums=[1]))
print(obj.maxSubArray(nums=[5, 4, -1, 7, 8]))
|