C++程序 用于确定具有最大和的子数组的大小

给定一个数组，找出具有最大和的子数组长度。

示例：

输入：a[]={1, -2, 1, 1, -2, 1}
输出：子数组长度为2
解释：连续元素并且最大和的子数组是{1, 1}。因此长度为2

输入：a[]={-2, -3, 4, -1, -2, 1, 5, -3}
输出：子数组长度为5
解释：连续元素并且最大和的子数组是{4, -1, -2, 1, 5}。

这个问题主要是最大子序列和的一个变化。

的想法是每当以0为结尾的总和变得小于0时更新开始索引。

// C++ program to print length of the largest
// contiguous array sum
#include<bits/stdc++.h>
using namespace std;
 
int maxSubArraySum(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0,
       start =0, end = 0, s=0;
 
    for (int i=0; i< size; i++ )
    {
        max_ending_here += a[i];
 
        if (max_so_far < max_ending_here)
        {
            max_so_far = max_ending_here;
            start = s;
            end = i;
        }
 
        if (max_ending_here < 0)
        {
            max_ending_here = 0;
            s = i + 1;
        }
    }
     
    return (end - start + 1);
}
 
/*Driver program to test maxSubArraySum*/
int main()
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(a)/sizeof(a[0]);
    cout << maxSubArraySum(a, n);
    return 0;
}  

输出 :

5

时间复杂度： O(N)，其中N是输入数组的大小。这是因为一个for循环从1到数组的大小执行。

空间复杂度： O(1)，因为没有使用额外的空间。