Maximum subarray problem

Common card · No. 259886

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 ) {\displaystyle O(n)} time and O ( 1 ) {\displaystyle O(1)} space. Formally, the task is to find indices i {\displaystyle i} and j {\displaystyle j} with 1 ≤ i ≤ j ≤ n {\displaystyle 1\leq i\leq j\leq n} , such that the sum ∑ x = i j A [ x ] {\displaystyle...

Read on Wikipedia · Image Snydergd, CC BY-SA 4.0