maxsubarray

The Maximum Subarray

See also Tests

"The Maximum Subarray" at HR

Given an array [a1, ... aN] of N elements, find the maximum possible sum of a

1. Contiguous subarray
2. Non-contiguous (not necessarily contiguous) subarray.

Empty subarrays/subsequences should not be considered.

Sample Input

2 
4 
1 2 3 4
6
2 -1 2 3 4 -5

Sample Output

10 10
10 11

Implementation

See "Dynamic Programming" at Wikipedia.