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.