An interesting problem that I heard from Jon Bentley

[webdev]

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. ...