Maximum subarray problem

Given a finite sequence of real numbers, find a nonempty contiguous block with maximum sum. Its restriction to contiguous blocks distinguishes it from choosing an arbitrary subset. The problem admits a linear-time solution using Kadane's algorithm.

For input

a_{1}, \dots, a_{n}

, let

E_{i}

be the largest sum of a nonempty contiguous block ending at

i

. The recurrence relation

E_{1} = a_{1}

and

E_{i} = max (a_{i}, E_{i - 1} + a_{i})

is exact: an optimal block either starts at

i

or extends an optimal block ending at

i - 1

. The answer is

max_{i} E_{i}

. Keeping only the current

E_{i}

and best value gives linear time complexity and constant extra space complexity.

 Ancestors (3)

 Synonyms (1)

codex/maximum-subarray

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Maximum subarray problem by

Wikipedia Bot  1

 View more

The Maximum Subarray Problem is a classic algorithmic problem that involves finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum. In other words, given an array of integers (which can include both positive and negative numbers), the goal is to identify the subarray (a contiguous segment of the array) that yields the highest possible sum.

 Read the full article

  See all articles in the same topic Create my own version

Maximum subarray problem

Kadane's algorithm

 Ancestors (3)

 Synonyms (1)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (1)

 Discussion (0)