代码拉取完成,页面将自动刷新
"""
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
"""
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
numsLen = len(nums)
dp = [nums[0]]
maxSubSum = nums[0]
i = 1
while i < numsLen:
if dp[i - 1] > 0:
temp = dp[i - 1]
else:
temp = 0
dp.append(nums[i] + temp)
if maxSubSum < dp[i]:
maxSubSum = dp[i]
i += 1
return maxSubSum
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。