Can Kadane Algo help us to find the sub array which give maximum sum

#1

If yes, tell a technique to find the maximum sum and sub array giving maximum sum all together having complexity less than n^2?

#2

@dhruvtrehan45,
Hello dhruv,
yes we can find the subarray whose sum is maximum in O(N).

a)you need two additional variable left and right which stores starting and ending index of subarray.
b) apply kadane algorithm on your array ,whenever you encounter max_sum_so_far < running_sum
- - - update ur max_sum_so_far and update left and right indices accordingly.

#3

@dhruvtrehan45
Hello dhruv,
checkout this code - https://ide.codingblocks.com/s/178258
feel free to ask any other doubt related to this problem

#4

@dhruvtrehan45
hello dhruv ,
if ur doubt is resolved then pls mark it as resolved

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.