这篇文章将为大家详细讲解有关怎么使用Python实现大子序和，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
在嘉定等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站制作、成都网站建设 网站设计制作按需求定制网站,公司网站建设,企业网站建设,品牌网站制作,全网整合营销推广,成都外贸网站制作,嘉定网站建设费用合理。描述
给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和大。
例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]，
连续子序列 [4,-1,2,1] 的和大，为 6。
我 v1.0
class Solution: def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ l = len(nums) i = 0 result = nums[0] while i < l: sums = [] temp = 0 for j in range(i, l): temp+=nums[j] sums.append(temp) if result < max(sums): result = max(sums) i+=1 return result
测试结果如下：
本地运行时间为14.7s，说明我的方法太粗暴了。应该寻找更好的算法。
我 优化后v1.1。优化方案，去掉sums数组，节省空间。但时间复杂度仍然不变。
l = len(nums) i = 0 result = nums[0] while i < l: temp = 0 for j in range(i, l): temp+=nums[j] if result < temp: result = temp i+=1 return result
仍然只通过200/202测试用例，仍然超出时间限制。但本地运行时间为8.3s。有进步。
别人，分治法。时间复杂度O(NlogN)
将输入的序列分成两部分，这个时候有三种情况。
1）大子序列在左半部分
2）大子序列在右半部分
3）大子序列跨越左右部分。
前两种情况通过递归求解，第三种情况可以通过。
分治法代码大概如下，emmm。。。目前还没有完全理解。
def maxC2(ls,low,upp): #"divide and conquer" if ls is None: return 0 elif low==upp: return ls[low] mid=(low+upp)/2 #notice: in the higher version python, “/” would get the real value lmax,rmax,tmp,i=0,0,0,mid while i>=low: tmp+=ls[i] if tmp>lmax: lmax=tmp i-=1 tmp=0 for k in range(mid+1,upp): tmp+=ls[k] if tmp>rmax: rmax=tmp return max3(rmax+lmax,maxC2(ls,low,mid),maxC2(ls,mid+1,upp)) def max3(x,y,z): if x>=y and x>=z: return x return max3(y,z,x)
动态规划算法，时间复杂度为O(n)。
分析：寻找最优子结构。
l = len(nums) i = 0 sum = 0 MaxSum = nums[0] while i < l: sum+=nums[i] if sum > MaxSum: MaxSum = sum if sum < 0: sum = 0 i+=1 return MaxSum
Oh！My god！！！ ！！！！！！！！运行只花了0.2s！！！！！！！！！！！！！！！这也太强了吧！！
优化后,运行时间0.1s.
sum = 0 MaxSum = nums[0] for i in range(len(nums)): sum += nums[i] if sum > MaxSum: MaxSum = sum if sum < 0: sum = 0 return MaxSum
其中
sum += nums[i]必须紧挨。
MaxSum = sum
关于“怎么使用Python实现大子序和”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
