Given an array nums that may contain negative numbers, return the largest possible sum of any non-empty contiguous subarray. Trying every subarray works, but re-summing overlapping ranges from scratch throws away most of the previous work. Kadane's AlgorithmKadane's AlgorithmA single-pass technique for the maximum-subarray-sum problem: at each element, decide whether to extend the running subarray or restart from here, based on whether the running sum has gone negative. answers this in one pass: keep a running sum, and whenever it dips below zero, abandon it and start over at the next element — a negative running total can never help a future subarray, so restarting is always at least as good as carrying it forward.