# 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.

## 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})$ 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})$ Exact Deterministic Time
Shamos 1978 $O(n \log n)$ $O(\log n)$ 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})$
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$