首页 > 代码库 > LEETCODE —— Maximum Subarray [一维DP]
LEETCODE —— Maximum Subarray [一维DP]
Maximum Subarray
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.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
--
一维DP, O(n).
假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值， 定义为Max[i], 在这里，当求取Max[i+1]时，
if (Max[i] + A[i+1] >0)
Max[i+1] = Max[i] + A[i+1]
if(Max[i]+A[i+1] <0) #也就是要舍弃
Max[i+1] = 0
‘‘‘Created on Nov 13, 2014@author: ScottGu<gu.kai.66@gmail.com, 150316990@qq.com>‘‘‘class Solution: # @param A, a list of integers # @return an integer def maxSubArray(self, A): sum=0 max=-655356 for x in A: sum+=x if(sum>max): max=sum if(sum<0): sum=0 return max
LEETCODE —— Maximum Subarray [一维DP]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。