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.

7 Years
Discussion Span
Last Post by 0x69

Yes, how about it? Would you care to try to solve it?

I asked the question because I think that trying to solve it may be educationally useful for pepole who are studying computer science.
