1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| '''
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
5 steps to DP:
1.subprobs: dp(i)-> maxsubarray in nums[:i]
2.guess: for each nums[i] add it or not.
3.recurrence: dp(i)=max(nums[i]+dp(i-1),nums[i])
4.order: for i=1,..,n: dp(i)
5.orig prob: dp(n)
'''
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
curSum = maxSum = nums[0]
for num in nums[1:]:
curSum = max(num, curSum + num)
maxSum = max(maxSum, curSum)
return maxSum
|
