我是靠谱客的博主 腼腆白昼,这篇文章主要介绍JZ42. 连续子数组的最大和,现在分享给大家,希望可以做个参考。

输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

示例:
 输入:[1, -2, 3, 10, -4, 7, 2, -5]
 返回值:18

思路:
要得到所给数组nums的连续子数组的最大和,我们可以依次计算出“以nums[0]为结束的最大子数组和”、“以nums[1]为结束的最大子数组和”、“以nums[2]为结束的最大子数组和”、……、“以nums[n]为结束的最大子数组和”。然后在它们之间选出的最大值,即为所给数组nums的连续子数组的最大和(和最大的连续子数组必然以数组当中的某个元素结束)。

第一步:定义一个数组sum,用于存放nums数组当中以某一元素为结束的最大子数组和。
在这里插入图片描述
第二步:分别计算以nums数组当中的不同元素为结束的最大子数组和。
sum[i]当中存储的是nums数组当中以nums[i]为结束的最大子数组和。以数组nums的第0个元素为结束的最大子数组和就是nums[0]其本身,即sum[0] = nums[0]。
而对于以数组nums的其他元素为结束的最大子数组和,应该等于“以其上一个元素为结束的最大子数组和加上该元素本身”和“该元素本身”这二者的较大值。例如,以元素nums[1]为结束的最大子数组和,应该等于“以nums[0]为结束的最大子数组和加上nums[1]”和“nums[1]”这二者的较大值。
在这里插入图片描述
据此,我们可以计算出sum数组的每一个元素的值,而sum数组当中的最大元素便是数组nums的连续子数组最大和。
在这里插入图片描述
代码如下:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution { public: int maxSubArray(vector<int>& nums) { vector<int> sum; sum.resize(nums.size()); //sum数组当中的元素个数与nums数组相同 sum[0] = nums[0]; //以第0个元素为结束的最大子数组和就是其本身 //依次计算sum数组当中的元素 for (int i = 1; i < sum.size(); i++) { sum[i] = max(sum[i - 1] + nums[i], nums[i]); } //选出sum数组的最大元素,即数组nums的连续子数组最大和 int max = sum[0]; for (int i = 1; i < sum.size(); i++) { if (sum[i] > max) max = sum[i]; } return max; //返回数组nums的连续子数组最大和 } };

最后

以上就是腼腆白昼最近收集整理的关于JZ42. 连续子数组的最大和的全部内容,更多相关JZ42.内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(85)

评论列表共有 0 条评论

立即
投稿
返回
顶部