forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaximum-subarray.py
More file actions
22 lines (20 loc) · 766 Bytes
/
maximum-subarray.py
File metadata and controls
22 lines (20 loc) · 766 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#https://leetcode.com/problems/maximum-subarray/
"""
[0]
if we know the max value of the subarray that ends at i index is Mi
what is the max value of the subarray that ends at i+1 index?
its either nums[i+1] or nums[i+1]+Mi
so code below, maxCurrent[i] stores the max value of subarray that ends at i
[1]
the max value of the subarray that ends at 0, has to be nums[0].
[2]
the max value of subarray must ends in one of the index of nums
so we get the max(maxCurrent).
"""
class Solution(object):
def maxSubArray(self, nums):
if nums==None or len(nums)==0: return None
maxCurrent = [nums[0]] #[1]
for i in xrange(1, len(nums)):
maxCurrent.append(max(nums[i], nums[i]+maxCurrent[-1])) #[0]
return max(maxCurrent) #[2]