Kadane algo doubt

#1

Whenever current sum becomes negative ,it is changed to 0. Pls explain.

#2

hi @vatsal50, when current sum becomes negative then there is no point to continue that subarray as we can have another subarray starting from i.

proof:
first u need to understand that what curr_sum represents, it represents the maximum cummulative sum of the subarray ending at i th index
if lets say we are at ith index and curr_sum<0;
now we need to compute curr_sum for ith index
we have two choices .

  1. to continue the previous subbarray making cur_sum=curr_sum+arr[i]
  2. to start a new subbarray from ith index by making curr_sum=0,then adding arr[i] to it , thus making curr_sum=arr[i].
    as you can easily see that ,since curr_sum was negative thus we get higher value if we take second choice .

this is a fairly easy concept try to dry run some examples by yourself

#3

hi,
is it mandatory that maximum sub array sum should be positive?
what if all elements in the array are negative?

#4

hi @vatsal50, the only case kadane’s algo will fail is when we have all the elements as negative so, in that case the answer would be simply the maximum element in the array

#5

can the final sub array have negative elements?

#6

what do you mean by final subarray ?

#7

the sub array which has maximum sum

#8

no, as the moment it will be negetive we will make it 0

#9

no, if we have to display the elements of sub array which has maximum sum
then it can have negative elements?

#10

yes, in that case the subarray can contain negative elements
you can refer : - https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane’s_algorithm
to get detailed explanation

#11

ok. thanks for help :blush: