Hosted by The Math Forum


Problem of the Week 862

A Programming Challenge

_____________________________________________
Spring 98 Archive || MacPOW Home || Math Forum POWs || Search MacPOW
_____________________________________________

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.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

The Math Forum

5 October 1998