To solve this problem, we want to find the subarray with the largest sum. It feels like we might be able to do this in one pass. The idea to doing this is to walk left to right, adding numbers to the current sum we've seen so far, and updating the maximum sum we've seen.

This works fine, until you realize we might actually make our sum negative. If our sum goes negative, then it means we should reset the sum, and start a new window starting at the next element. This is because starting out with a negative sum will always be worse than starting a new sum from scratch.

Putting these two ideas together gives us the full solution. Here's the code:

Time Complexity O(n). We need to loop through every element in the array.

Space Complexity O(1). We store two numbers, which is O(2) = O(1).

For historical reasons this algorithm is called Kadane's Algorithm, although it' not a very interesting algorithm.