0
$\begingroup$

I'm trying to solve the contiguous subarray problem on CodeSignal & I came up with the following solution which is based off of Kadane's Algorithm. My implementation passed the given test data set however upon submission, it failed. There's no reason given on CodeSignal & I can't look at it since I just started doing it & have less coins.

I can't figure out why my solution is failing but the solution based on online pseudo code works, even though my solution passed the preliminary tests. I think it might have to do with integer overflow or some other reason that's why I've come here to seek help from experts.

My implementation:

 public int findConsecutiveSubarray(int nums[]) {
    int currentSum = 0;
    int max =Integer.MIN_VALUE;;

    int i=0;
    while(i < nums.length) {
        currentSum += nums[i];

        if(max < currentSum)
            max = currentSum;

        if(max < nums[i]) {
            max = nums[i];
            currentSum = nums[i];
        }

        i++;
    }
    System.out.println("maxSum : "+ max);
    return max;
}

Solution based on online:

int arrayMaxConsecutiveSum2(int[] nums) {
        int currentMax = 0;
        int globalMax = 0;
        
        globalMax = currentMax = nums[0];
        
        for(int i=1; i<nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            globalMax = Math.max(globalMax, currentMax);
        }
    
    return globalMax;
}
$\endgroup$
2
  • $\begingroup$ what is the precise definition of the question? $\endgroup$
    – nir shahar
    Jun 23, 2020 at 17:05
  • $\begingroup$ Coding questions and requests for help with your code are off-topic here. $\endgroup$
    – D.W.
    Jun 23, 2020 at 17:42

1 Answer 1

1
$\begingroup$

The issue is that you might not enter the second "if" when the current sum is smaller than nums[i]. Imagine, e.g., that at the beginning of the iteration you have currentSum=-5, max=100, nums[i]=10. At the end of the iteration you have currentSum=5 and max=100, yet the desired state is currentSum=10, max=100.

A corresponding instance where your algorithm fails is: 100, -105, 10, 95.

To fix this, the condition of the second "if" should be currentSum < nums[i].

Notice that, once you change this condition, you'll also have to revise other parts of your code accordingly: you can no longer unconditionally assign max to nums[i] in the body of the second "if" statement. This can be easily fixed by removing that assignment and swapping the order of your two ifs.

[...]
        if(currentSum < nums[i])
            currentSum = nums[i];

        if(max < currentSum)
            max = currentSum;        
[...]
$\endgroup$
2
  • $\begingroup$ Thanks for the detailed answer. Really appreciate it! One more question, how did you find out this problem & come up with a dataset as well? I'd like to learn this so in future, I can find such loop holes myself. $\endgroup$ Jun 24, 2020 at 10:01
  • $\begingroup$ The problem is a classic problem in computer science. See Maximum Subarray Problem on Wikipedia. I didn't come up with a dataset, I just read your code. $\endgroup$
    – Steven
    Jun 24, 2020 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.