if in this approach, all the inputs are negative integers then the answer comes out to be zero. Shouldn’t it be the smallest negative integer instead.
Maximum Subarray Sum 1, all negative inputs
Hello @zabhishek kadanes algorithm is to find the maximum sum subarray so if all the elements are negative in it then can there be resulted subarray of sum greater then 0 because 0 is the maximum sum out of them.
you can judge by this ;
if the subarray sum is -1 and the subarray sum is 1 then which is maximum of them:
0 is maximum that is why 0 is the answer:
if you have any doubt you can ask here:
Happy Learning!!
Please elaborate, As per this algorithm the result will be zero that I understand. But, logically if all numbers are negative like -5 -7 -3 -6 -8. And we find the maximum sum subarray, then shouldn’t the answer be -3 in this case.?
Hello @zabhishek okay you think -3 should be the answer then can you explain how do you find the answer should be -1?
then i will try to correct it.
please elaborate.
By “smallest negative integer”, I meant the smallest number out of the negative inputs not -1.
@zabhishek yes i got it but in kadanes eccen if all the numbers are negative then the subarray with the maximum sum would subaray with zero elements so that the sum will be also zero.
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.