剑指 Offer 42. 连续子数组的最大和(java+python)

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为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

思路

遍历数组，存放当前连续子数组最大和sum为res，
若sum大于0加上下一个i
→sum+=num
否则则sum从i重新计算
→sum=num
若sum>res则更新res

java

class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int sum=0;
for(int num:nums){
if(sum>0) sum+=num;
else sum=num;
res=Math.max(sum,res);
}
return res;
}
}

python

class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res,sum=nums[0],0
for num in nums:
if sum>0:
sum+=num
else:
sum=num
if sum>res:
res=sum
return res

最后

以上就是灵巧口红为你收集整理的剑指 Offer 42. 连续子数组的最大和(java+python)的全部内容，希望文章能够帮你解决剑指 Offer 42. 连续子数组的最大和(java+python)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。