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

Currently no algorithms in our database for the given problem.

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