Given an array like [-1, 2, -3, 4, 1, -2, 4]
Find the subarray with the largest sum. In this case the largest sum is 7. The subarray that gives this largest sum is [4, 1, -2, 4].
This is called Kadane's Algorithm and requires O(1) memory and O(n) runtime. You cannot get faster than this for this problem.
Here is a challenge for you:
Right now it does not work if all of the numbers are smaller than 0. Can you make it work with all negative numbers?