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.
Javascript
<script>
// JavaScript program to print length
// of the largest contiguous array sum
function maxSubArraySum(a, size)
{
let max_so_far = Number.MIN_VALUE,
max_ending_here = 0,start = 0,
end = 0, s = 0;
for(let 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 code
let a = [ -2, -3, 4, -1, -2, 1, 5, -3 ];
let n = a.length;
document.write(maxSubArraySum(a, n));
// This code is contributed by splevel62
</script>
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