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.
Python3
# Python3 program to print largest contiguous array sum from sys import maxsize # Function to find the maximum contiguous subarray # and print its starting and end index def maxSubArraySum(a,size): max_so_far = -maxsize - 1 max_ending_here = 0 start = 0 end = 0 s = 0 for i in range(0,size): 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 a = [-2, -3, 4, -1, -2, 1, 5, -3] print(maxSubArraySum(a,len(a)))
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