Maximum subarray problem

Article summary

[[File:Maximum Subarray Visualization.svg|thumbnail|Visualization of how sub-arrays change based on start and end positions of a sub-array. Each colored line corresponds to a fixed starting index in the array. The leftmost point of a line represents the single-element sub-array starting at that index, and each subsequent point extends the sub-array by one element to the right. The x-coordinate of a point is the index of the last element in the sub-array, and the y-coordinate is the sum of the sub-array. In this case, the original array from which sub-arrays are taken is [2, 3, -1, -20, 5, 10]. In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. It can be solved in O(n) time and O(1) space. Formally, the task is to find indices i and j with 1 \leq i \leq j \leq n , such that the sum : \sum_{x=i}^j A[x] is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, the sum of all values of the empty subarray is zero.) Each number in the input array A could be positive, negative, or zero.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.