Maximum Subarray Sum

#1

I tried to solve the question using modified kadane’s algo (so that it takes all negative number case too) it’s working fine with all the cases I’m entering but it’s not passing any case when I submit my code. I tried to rectify it but nothing helped.

Here’s the code:

#2

No need to modify kadane’s algorithm

This is Wrong statement
currentSum = max(arr[i], currentSum + arr[i]);

correct statement is like this

            currentSum = currentSum + arr[i];

            if(currentSum<0)

                currentSum = 0;

for input
4
-1 -2 -3 -4
Correct output is 0
(for empty subarray)

#3

Actually I asked a doubt before to tackle all negative value case since kadane’s algo doesn’t work for that and I got this modified algorithm in reply. I tried it and it’s working for negative numbers and all cases I entered, but not when I submit the code.
Here’s the link to that query: Tackling all Negative values array in Kadane algo

#5

I did the changes as you suggested still all the test cases are failing…
Here’s the code: https://ide.codingblocks.com/s/597089

#6

currentSum and max sum should be initialize inside for loop every time

int maxSum = INT_MIN, currentSum = 0;

Modified Code

i can’t test this code because i didn’t find the question in hackerBlocks
can you share the question link if this code doesn’t pass testcases

#7

Yes, now the code is working for both classical and modified kadane :slight_smile:
Thanks a lot!! I didn’t noticed the presence of initialization of maxSum and currentSum outside the for loop.

#8

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.