题目描述
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
本题使用动态规划的思想,定义 f(i) 为以第 i 个数字结尾的子数组的最大和。那么答案就是:
首先 f(0) 肯定等于数组中的第一个数的值,然后往后递推。到第 i 个数字时,我们可以假设当前这个数字一定会存在于最大和的序列中,但是我们要判断是不是要加上前面 i-1 个数字,也就是说要考虑第 i 个数字单独成一段还是要加上 f(i-1) 组成一个新的序列。那么递推式就出来了:
每次递推到一个新的数字时,将最大结果保存下来,避免陷入局部最优。代码如下:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res,max_num=0,nums[0]
for i in nums:
res=max(res+i,i)
max_num=max(max_num,res)
return max_num