最大和的子数组

[编程题]最大和的子数组

热度指数：14989 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请计算给出的数组（至少含有一个数字）中具有最大和的子数组（子数组要求在原数组中连续）

例如：给出的数组为[−2,0,−3,4,−2,2,2,−5,4],

子数组[−2,0,−3,4,−2,2,2,−5,4],具有最大的和:6.

示例1

输入

[1]

输出

示例2

输入

[−2,0,−3,4,−2,2,2,−5,4]

输出

算法知识视频讲解

王清楚

发表于 2020-05-03 10:44:30

题面描述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。题解如果已知以位置$结尾的子数组的最大和，怎么求以位展开全文

华科不平凡

发表于 2020-09-03 11:04:58

两种方法—— 贪心思维，设arr[i]为以元素i结尾的子数组的最大和，那么arr[i] = max(arr[i-1]+nums[i], nums[i])，最大的arr[i]即是答案分治思维，思路很简单，最大子数组和要么存在于左侧区间，要么存在于右侧区间，要么存在于跨越左右侧的区间显然，贪心法展开全文

Sunmerhater

发表于 2020-06-11 15:45:37

题目描述请计算给出的数组（至少含有一个数字）中具有最大和的子数组（子数组要求在原数组中连续）例如：给出的数组为[−2,1,−3,4,−1,2,1,−5,4],子数组[−2,1,−3,4,−1,2,1,−5,4],具有最大的和:6. 解题参考网上：思路：如果累加为负则抛弃重置为下一个置，但需要保存之前展开全文