1D Maximum Subarray

Given an array $A$ of length $n$ , find $i, j$ with $1\leq i \leq j \leq n$ maximizing $\sum^j_{x=i} A[x]$ , that is, find a contiguous subarray of $A$ of maximum sum

Parameters

$n$ : length of array

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 6 of 6 algorithms


Bird	1989	$O(n)$	$O(1)$ auxiliary
Kadane's Algorithm	1982	$O(n)$	$O(1)$
Shamos	1978	$O(n \log n)$	$O(\log n)$
Brute Force	1977	$O(n^3)$	$O(1)$
Grenander	1977	$O(n^2)$	$O(n)$
Faster Brute Force (via x[L:U] = x[L:U-1]+x[U])	1977	$O(n^2)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms