Difference between revisions of "Maximum subvector sum"

From PEGWiki
Jump to: navigation, search
(Created page with "The '''maximum subvector sum''' problem is that of finding a segment of a vector (array of numbers)<ref>In computer science, ''vector'' is often used to mean ''array of real ...")
(No difference)

Revision as of 19:36, 18 April 2012

The maximum subvector sum problem is that of finding a segment of a vector (array of numbers)[1], possibly empty, with maximum sum. If all elements of the array are nonnegative, then the problem may be trivially solved by taking the entire vector; if all elements are negative, then the problem is again trivially solved by taking the empty segment (whose sum is conventionally defined to be zero). The problem requires more thought, however, when the vector contains a mixture of positive and negative numbers.

Notes and references

  1. In computer science, vector is often used to mean array of real numbers; sometimes it is simply synonymous with array. This meaning is related to but different from the meaning of the word in mathematics and physics.