Maximum Subarray (Kadane's Algorithm)
medium⏱ 15 mintypescriptchallengesproblem-solving-intermediate-
Caso de ejemplo — tu programa lee de stdin e imprime en stdout.
Find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Use Kadane's Algorithm: Track current sum and max sum. If current sum becomes negative, reset it.
Example: [-2,1,-3,4,-1,2,1,-5,4] → Subarray [4,-1,2,1] has largest sum = 6
Formato de entrada
Line 1: n. Line 2: n space-separated integers.
Formato de salida
The maximum subarray sum.
Restricciones
1 ≤ n ≤ 10⁵, -10⁴ ≤ nums[i] ≤ 10⁴