You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
'''
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：输入：[-2,1,-3,4,-1,2,1,-5,4] 输出：
'''
class Solution ( object ) :
def _maxSubArray ( self , nums ) :
"""
:type nums: List[int]
:rtype: int
"""
if len ( nums ) == 0 :
return 0
preSum = maxSum = nums [ 0 ]
for i in xrange ( 1 , len ( nums ) ) :
preSum = max ( preSum + nums [ i ] , nums [ i ] )
maxSum = max ( maxSum , preSum )
return maxSum
def maxSubArray ( self , nums ) :
if len ( nums ) == 0 :
return 0
preSum = maxSum = nums [ 0 ]
for i in xrange ( 1 , len ( nums ) ) :
preSum = ( preSum + nums [ i ] if preSum > 0 else nums [ i ] ) # 类似三目运算符
maxSum = max ( maxSum , preSum )
return maxSum
def maxSubArray ( self , nums ) :
for i in range ( 1 , len ( nums ) ) :
nums [ i ] = nums [ i ] + max ( nums [ i - 1 ] , 0 )
return max ( nums )
