1
$\begingroup$

Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting subarray that produces the corresponding maximum sum?

PS: I don't know whether I should post this here, or Stack Overflow, or both.

$\endgroup$
1
$\begingroup$

Yes, you can.

Kadanes's algorithm keeps the value of the best subarray in a variable, let's call it best_sum. Notice the invariant in the algorithm. best_sum will always (after each iteration) contain the value of the maxium subarray of the prefix of the array that you already visited. Additionally you know the best suffix sum of the current prefix, let's call it current_sum, which you use to update best_sum.

You just need to do the same thing with the position. Introduce three more variables current_startindex, best_startindex and best_endindex. current_startindex tells you, at which position the current best suffix starts. best_startindex and best_endindex indicate the start and end of the best subarray from the visited prefix. Keep those variables valid in each iteration. E.g. Whenever you update current_best, also update current_startindex. And whenever you update best_max, also update the best_startindex and best_endindex, so that at the end of each iteration the value is correct.

After iterating over the complete array, best_sum will contain the sum of values of the maximum subarray, and best_startindex and best_endindex will tell you the positions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.