function kadane(arr: number[]): number {
let max = arr[0], current = arr[0];
for (let i = 1; i < arr.length; i++) {
current = Math.max(arr[i], current + arr[i]);
max = Math.max(max, current);
}
return max;
}
console.log(kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]));📥 Inputs:
❓ ¿Cuál es el output?
Ingresa tu respuesta abajo
💡 Explicación
¡Falso! El algoritmo de Kadane tiene una complejidad temporal de O(n), no O(n²). Es uno de los algoritmos más elegantes de programación dinámica, resolviendo el problema de subarreglo de suma máxima en una sola pasada. La solución naive que prueba todos los subarreglos posibles sí es O(n²). Salida: 6 (subarreglo [4, -1, 2, 1])
¿Verdadero o Falso? 🤔