Se da un arreglo, encuentre la longitud del subarreglo que tiene la suma máxima.
Ejemplos:
Input : a[] = {1, -2, 1, 1, -2, 1}
Output : Length of the subarray is 2
Explanation: Subarray with consecutive elements
and maximum sum will be {1, 1}. So length is 2
Input : ar[] = { -2, -3, 4, -1, -2, 1, 5, -3 }
Output : Length of the subarray is 5
Explanation: Subarray with consecutive elements
and maximum sum will be {4, -1, -2, 1, 5}.
Este problema es principalmente una variación del problema de subarreglo contiguo de suma más grande .
La idea es actualizar el índice inicial cada vez que la suma que termina aquí sea menor que 0.
C++
// 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;
}
Producción :
5
Consulte el artículo completo sobre Tamaño del subarreglo con suma máxima para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA