You are given a one-dimensional array of signed integers. Find the (contiguous) subarray with the largest sum.
If none of the array elements are negative, the solution is obviously that the subarray is equal to the entire array, so the problem is interesting only if the integers are signed.
There is an obvious solution with run time of order n^3, where n is the number of elements in the array: Generate every subarray, sum each subarray's elements, and keep track of the one with the biggest sum you've seen so far. So the interesting part of the problem is to see if you can do better than order n^3, and how much better you can do.
