https://leetcode.com/problems/maximum-subarray/#/description
Paste_Image.png
說(shuō)明
- 查找連續(xù)子數(shù)組筹吐，使之sum最大
思路
- 初始化maxSum = a[0], curSum = a[0]
- 如果 curSum > 0 則curSum = curSum + a[i]
- 如果 curSum < 0 則 curSum = a[i]
- maxSum = max(maxSum, curSum)
# Time O(n)
# Space O(1)
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
curSum = nums[0]
maxSum = nums[0]
for i in range(1, len(nums)):
if curSum >= 0:
curSum = curSum + nums[i]
else:
curSum = nums[i]
maxSum = max(maxSum, curSum)
return maxSum
