MaxArraySum using Kadane's algorithm

#1

I am always getting error at Testcase 1 - Wrong Answer. However my code is giving the correct answer (I unlocked and downloaded TestCases to confirm).
My code is as follows:
#include
using namespace std;

int main() {

int TC = 0;

cin >> TC;
int maxSum = 0;
for (int idx =0 ; idx < TC; idx ++){
int N;

cin>> N;
int currSum = 0;


int temp;
cin >> temp;
maxSum = temp;
currSum = temp;
for (int idxj = 1; idxj < N; idxj ++ ) {
  cin >> temp;
  currSum += temp;
  
    
 maxSum = max(currSum, maxSum);
}

}
cout <<maxSum;
return 0;
}

#2

Hey, your code is not correct, you are supposed to calculate the max subarray sum for each test case. You have missed one more condition also if(current_sum < 0) then assign current_sum=0; . Here, I have corrected your code, you can refer this code snippet.

int main() {
int TC = 0;
cin >> TC;
for (int idx =0 ; idx < TC; idx ++){
long long int N;
cin>> N;
long long int currSum = 0;
long long int maxSum = 0;
long long int temp;
maxSum = 0;
currSum = 0;
for (int idxj = 1; idxj <= N; idxj++ ) {
    cin >> temp;
    currSum += temp;
    if (currSum < 0)
        currSum = 0;
    maxSum = max(currSum, maxSum);
}
    cout <<maxSum<<endl;
}
    return 0;
}
#3

Hi Sanjeet, Thanks. But I believe the lecture is in error to initialize the max_sum to 0. Instead, it should be INT_MIN from climits.h. For example, the following input where all elements are negative, the answer is 0 which is incorrect. Correct answer is -3.

1
13
-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7

Reference: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

#4

Adding maxSum = INT_MIN and re-ordering the maxSum computation before the currentSum reset to 0 fixed this problem.

#include<iostream>
#include<climits>
using namespace std;
int main() {
   int TC = 0;
   cin >> TC;
   for (int idx =0 ; idx < TC; idx ++){
      long long int N;
      cin>> N;
      long long int currSum = 0;
      long long int maxSum = INT_MIN;// instead of setting to 0
      long long int temp;
      //maxSum = 0;
      //currSum = 0;
        for (int idxj = 1; idxj <= N; idxj++ ) {
            cin >> temp;
            currSum += temp;
            maxSum = max(currSum, maxSum); // maxSum is updated here 
            if (currSum < 0)
                currSum = 0;

      }
      cout <<maxSum<<endl;
   }
   return 0;
}
#5

Also fixed for MaxSubarrays Sum 2:

https://ide.codingblocks.com/s/56558

#6

Hey, you are right but in video lecture the case when all the elements of the array are negative is not considered.

#7

Hey Sriram, as you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required. And please mark your doubts as resolved in your course’s “Ask Doubt” section, when your doubt is resolved.