Fast computation of maximum sum subarray

Fast computation of the maximum subarray sum of a vector using Kadane's algorithm. The implementation handles purely negative numbers.

maximum_subarray(x)

Arguments

x

A vector

Value

A list with three elements: sum (the maximum subarray sum), start (the starting index of the subarray) and end (the ending index of the subarray)

Author

Claus Ekstrom <claus@rprimer.dk>

Examples

maximum_subarray(1:4)
#> $sum
#> [1] 10
#> 
#> $start
#> [1] 1
#> 
#> $end
#> [1] 4
#> 

maximum_subarray(c(-2, 1, -3, 4, -1, 2, 1, -5, 4))
#> $sum
#> [1] 6
#> 
#> $start
#> [1] 4
#> 
#> $end
#> [1] 7
#> 
 
maximum_subarray(rnorm(100000))
#> $sum
#> [1] 203.8109
#> 
#> $start
#> [1] 70716
#> 
#> $end
#> [1] 84112
#>