You can answer this question from CLRS, which includes a tip:
Use the following ideas to develop a nonrecursive, linear-time algorithm for the
maximum-subarray problem.
Start at the left end of the array, and progress toward
the right, keeping track of the maximum subarray seen so far.
Knowing a maximum sub array of A[1..j]
, extend the answer to find a maximum subarray ending at index j+1
by using the following observation:
a maximum sub array of A[1..j+1]
is either a maximum sub array of A[1..j]
or a sub array A[i..j+1]
, for some 1 <= i <= j + 1
.
Determine a maximum sub array of the form A[i..j+1]
in constant time based on knowing a maximum subarray ending at index j
.
max-sum = A[1]
current-sum = A[1]
left = right = 1
current-left = current-right = 1
for j = 2 to n
if A[j] > current-sum + A[j]
current-sum = A[j]
current-left = current-right = j
else
current-sum += A[j]
current-right = j
if current-sum > max-sum
max-sum = current-sum
left = current-left
right = current-right
return (max-sum, left, right)
Kadane's algorithm
maxsum()
that implements Kadane's algorithm and its modificationmaxsumseq()
that computes indexes and returns the subsequence from Greatest subsequential sum problem.