Maximum Subarray (Maximum Subarray Problem)

Description

Given a $d$-dimensional array $M$ with $n^d$ real-valued entries, find the $d$-dimensional subarray of $M$ which maximizes the sum of the elements it contains.

Related Problems

Subproblem: 1D Maximum Subarray, 2D Maximum Subarray, Maximum Square Subarray

Related: 2D Maximum Subarray, Maximum Square Subarray

Parameters

n: length of array

d: dimensionality of array

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Brute Force	1977	$O(n^{3})$	$O({1})$ auxiliary	Exact	Deterministic
Grenander	1977	$O(n^{2})$	$O(n)$	Exact	Deterministic
Faster Brute Force (via x(L:U) = x(L:U-1)+x(U))	1977	$O(n^{2})$	$O({1})$ auxiliary	Exact	Deterministic	Time
Shamos	1978	$O(nlogn)$	$O(log n)$ auxiliary	Exact	Deterministic
Kadane's Algorithm	1982	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic
Perumalla and Deo	1995	$O(log n)$	$O(n)$ auxiliary	Exact	Parallel	Time
Gries	1982	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic	Time
Bird	1989	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic	Time
Ferreira, Camargo, Song	2014	$O(log n)$	$O(n)$ auxiliary	Exact	Parallel	Time

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
Distance Product	if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ then: from-time: $O(n^{3-\epsilon})$	1998	https://dl.acm.org/doi/abs/10.5555/314613.314823	link
Negative Triangle Detection		1998	https://dl.acm.org/doi/abs/10.5555/314613.314823	link

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
Negative Triangle Detection		2018	https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.4	link
Max-Weight k-Clique	if: to-time: $O(n^{d+\lfloor d/{2}\rfloor-\epsilon})$ for $d$-dimensional hypercube arrays then: from-time: $O(n^{k-\epsilon})$ on $n$ vertex graphs for $k=d+\lfloor d/{2}\rfloor$	2016	https://arxiv.org/pdf/1602.05837.pdf	link