剑指 JZ85 连续子数组的最大和(二)

72 阅读 0 评论 48 点赞

我是靠谱客的博主唠叨柚子，最近开发中收集的这篇文章主要介绍剑指 JZ85 连续子数组的最大和(二)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

连续子数组的最大和(二)_牛客题霸_牛客网

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。

1.子数组是连续的，比如[1,3,5,7,9]的连续子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是连续子数组

2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个

3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组

4.返回的数组不计入空间复杂度计算

数据范围:

1<=n<=10^51<=n<=105

-100 <= a[i] <= 100−100<=a[i]<=100

要求:时间复杂度O(n)O(n)，空间复杂度O(n)O(n)

进阶:时间复杂度O(n)O(n)，空间复杂度O(1)O(1)

示例1

输入：[1,-2,3,10,-4,7,2,-5]

返回值：[3,10,-4,7,2]

示例2

输入：[1]

返回值：[1]

示例3

输入：[1,2,-3,4,-1,1,-3,2]

返回值：[1,2,-3,4,-1,1]

示例4

输入：[-2,-1]

返回值：[-1]

先审题，有两点需要明确，1、这个最大和允许连续子数组中有负数，也就是它的和可以加着加着变小了，后面又涨回来，2、不同起点的最大和连续子数组，取长度最大的那个，同一个起点出发，也有可能存在两个终点满足最大和，仍然取长度最大的那个。

解题思路：

1、首先遍历数组中的元素找到最大和，找最大和这一步，不用去考虑是否长度最大，定义一个变量来累加和，定义个变量，表示当前的最大和，要满足最大和，则当出现和小于0的时候前面的就不需要考虑在内了，因为在当前值上叠加小于0的和，不会比当前值本身更大。当累加和大于等于当前最大和的时候，更新当前最大和，且记录连续子数组的最后一个位置，

2、找到最大和之后，因为可能存在多个最大和，因此再遍历一次，记录每一次出现最大和的数组末尾位置

3、对每一个末尾位置，往前遍历，找到满足最大和的连续的子数组的最大长度，并记录起始位置和结束位置

3、返回起始位置和结束位置里的所有元素

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
// write code here
vector<int> res;
int n = array.size();
int maxsum = array[0];
int sum = 0;
int idx = 0;
for(int i=0;i<n;i++)
{
if(sum<0)
{
sum = array[i];
}
else
{
sum += array[i];
}
if(sum>=maxsum)
{
maxsum = sum;
idx = i;
}
}
vector<int> dp(n,0);
sum = 0;
for(int i=0;i<=idx;i++)
{
if(sum<0)
{
sum = array[i];
}
else
{
sum += array[i];
}
if(sum==maxsum)
{
dp[i] = 1;
}
}
int beginidx = 0;
int endidx = 0;
int length = 0;
int maxlength = 1;
for(int i=idx;i>=0;i--)
{
if(dp[i]==1)
{
int temp = maxsum;
int begin = 0;
for(int j=i;j>=0;j--)
{
temp -= array[j];
if(temp==0)
{
length = i-j+1;
begin = j;
}
}
if(length>=maxlength)
{
maxlength = length;
endidx = i;
beginidx = begin;
}
}
}
for(int i=beginidx;i<=endidx;i++)
{
res.push_back(array[i]);
}
return res;
}
};