Content deleted Content added
The lead should mention that it can be solved efficiently |
→top: mentioning complexity once in the lead is sufficient |
||
Line 2:
[[File:Maximum Subarray Visualization.svg|thumbnail|Visualization of how sub-arrays change based on start and end positions of a sample. Each possible contiguous sub-array is represented by a point on a colored line. That point's y-coordinate represents the sum of the sample. Its x-coordinate represents the end of the sample, and the leftmost point on that colored line represents the start of the sample. In this case, the array from which samples 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 data structure|array]] A[1...n] of numbers
Formally, the task is to find indices <math>i</math> and <math>j</math> with <math>1 \leq i \leq j \leq n </math>, such that the sum
| |||