Kadens Algo can we get sub-array?

#1

Kadens algo only finds the maximum sum from the array but what if we want to print the sub-array also then?

#2

Hi @vashish888, yes you can do that just keep a track of the indices wherever you are changing the value of max_so_far to max_ending_here and of max_ending_here to 0.
At the end you will get the indices and then you can print that portion of the array.

#3

@proRram What if all the elements in the array are -ve integers then kadens Algo will fail isn’t it?

#4

Ok so in that case you know the max sum will be the smallest negative number. And the position or the subarray will be an array containing that one number, the largest integer or i should say smallest negative number. For example:

// Input
5
-5, -2, -1, -3, -6
// Output
Max sum = -1
Starting at 2
Ending at 2

Hope this helps :slight_smile: