This past weekend saw our in-house ACM programming competition, which determines the team for the regionals next fall. In honor of that, we present a programming problem, for which my source is Don PIele, Univ. of Wisconsin, Parkside. He used this problem in the most recent issue of Quantum.
Suppose you are given an ordered list of 5000 numbers between -50 and 50. Determine the subset of consecutive entries that has the largest sum.
For example, if the list is
{-2, 10, -3, 0, -7, -5, -8, -7, 8, 7, -10, 2, 4, 3, 3, -9, -2, -1, 2, 2}
the answer would be "9 through 15" since those entries sum to 17 and that is the largest.
For definiteness, you can try your program on the 5000 numbers obtained by looking at the first 5000 primes, looking at the rightmost two digits only, and subtracting 50. Of course, these aren't random and span [-50, 49], but it will do as a sample.
In Mathematica, get this data set by: Mod[Prime[Range[5000]],100] - 50
© Copyright 1998 Stan Wagon. Reproduced with permission.