I’ve just opened Introduction to Algorithms on Divide-and-Conquer chapter, and found interesting item – The maximum-subarray problem. In book you can find implementation with complexity O(NlogN) with good explanation, but in Exercises part there is good task:

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 subarray of A[1..j] , extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of A[1..j+1] is either a maximum subarray of A[1..j] or a subarray A[i..j+1], for some 1<=i<=j+1. Determine a maximum subarray of the form A[i..j+1] in

constant timebased on knowing a maximum subarray ending at index j .

So, That is easy, because there are some ideas, you just need to stop and think a bit and all will be clear …

As described in the book you need to return 3 params

– max sum

– start index of sub array

– end index of sub array

OK, lets go …

Firstly create return structure.

[crayon-5bf06dc6e59a7939064543/]
After that try to create algorithm.

[crayon-5bf06dc6e59b4968365733/]
OK, what algorithm is doing:

– firstly run throughout all array

[crayon-5bf06dc6e59ba574398421/]
– skipping negative values and move start index

[crayon-5bf06dc6e59be350827840/]
– just add next value to current sum

[crayon-5bf06dc6e59c1595011596/]
– check if current sum > result value, if yes, assign sum to result and move end to current index

[crayon-5bf06dc6e59c5862268670/]
– and last one if sum < 0 assign 0 to sum and move start to next index

[crayon-5bf06dc6e59c9798137791/]
So, that is all 🙂