描述
给定一个序列（至少含有 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,最大子序和
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。