[LeetCode] 053. Maximum Subarray

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Dada una matriz de enteros números, find the subarray with the largest sum, and return its sum.

Ejemplo 1:

Aporte: nums = [-2,1,-3,4,-1,2,1,-5,4]
Producción: 6
Explicación: The subarray [4,-1,2,1] has the largest sum 6.

Ejemplo 2:

Aporte: nums = [1]
Producción: 1
Explicación: The subarray [1] has the largest sum 1.

Ejemplo 3:

Aporte: nums = [5,4,-1,7,8]
Producción: 23
Explicación: The subarray [5,4,-1,7,8] has the largest sum 23.

Restricciones:

1 <= números.longitud <= 10 ⁵
-10⁴ <= nums[i] <= 10⁴

Hacer un seguimiento: If you have figured out the En) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Pitón

				
					class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxNum = -100000
        sum = 0
        for i in range(len(nums)):
            sum += nums[i]
            if sum < nums[i]:
                sum = nums[i]
            maxNum = max(sum, maxNum)
        return maxNum

Medio

Pitón

Artículos relacionados