LeetCode 53 Maximum Subarray Sum - Implementation

Kadane's algorithm maintains the maximum sum ending at each position. If adding the current element makes the sum negative, restart. Initialize $current = 0$, $best = -\infty$. For each element: $current = \max(nums[i], current + nums[i])$, then $best = \max(best, current)$. Example: $[-2, 1, -3, 4, -1, 2, 1, -5, 4]$. The maximum subarray is $[4, -1, 2, 1]$ with sum $6$. Time: $O(n)$, Space: $O(1)$. This is optimal for the problem.

Time complexity: $O(n)$.

Space complexity: $O(1)$.