-
Notifications
You must be signed in to change notification settings - Fork 0
/
max_subarray.py
30 lines (24 loc) · 946 Bytes
/
max_subarray.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
'''
Question: https://leetcode.com/problems/maximum-subarray/
'''
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
'''
Use Kadane's Algorithm
TC: O(n)
SC: O(1)
'''
# init `curSum` and `maxSum` to first element in `nums`
curSum = maxSum = nums[0]
# iterate through all elements in nums starting from 2nd postion
for n in nums[1:]:
# if the ongoing sum is negative, it will not serve any purpose, so we drop the sum, and make it 0
if curSum < 0:
curSum = 0
# add the current number to ongoing sum `curSum`
# Note: if the above if condition is satisfied (if `curSum` is negative), the curSum will start from
# current number `n`
curSum += n
# we have to update the overall maxSum
maxSum = max(maxSum, curSum)
return maxSum