My code is accepted by leetcode. But I think it will give a wrong answer for this test case: A=[-2,3,-2,4]


  • -1
    O
    public class Solution {
    public int maxSubArray(int[] A) {
    	int maxSum = Integer.MIN_VALUE;
    	int curSum = 0;
    	for(int i = 0; i < A.length; i++)
    	{
    		curSum = curSum + A[i];
    		maxSum = Math.max(maxSum, curSum);
    		if(curSum < 0)
    			curSum = 0;
    	}
    
    	return maxSum;
    }
    

    }

    For the above code, I think the result is 4 for given A=[-2,3,-2,4].If yes, it's wrong. But why the code past the test?


  • 2

    I've tried your code, and it returns the correct result 5 for input [-2,3,-2,4].


  • 1
    M

    The algorithm you gave is absolutely correct.

    i  maxSum   curSum  A[i]
    0   MIN       0     -2       curSum+A[i]=-2<0, curSum=0  --> 0>MIN, maxSum=0
    1     0       0      3       curSum+A[i]= 3>0, curSum=3  --> 3>0, maxSum=3
    2     3       3     -2       curSum+A[i]= 1>0, curSum=1  --> 1<3, maxSum=3
    3     3       1      4       curSum+A[i]= 5>0, curSum=5  --> 5>3, maxSum=5
    4     5       5              i == A.length.  End loop. Return maxSum=5.

  • 0
    O

    Thanks, I made a mistake when thought the test case. You are right.


  • 0
    O

    Thanks, you are right


  • 0
    J

    could you please explain why the algorithm works?


  • 0
    O

    I think the algorithm goes through the element in the array one by one. every time we visit a new element, add it, to see if the current sum is larger than the recorded maximum sum. if current sum goes down or less than zero, it means the element we visit is negative. So we don't need this element, the parsing process will start from the element that is next to this negative and we set current sum is zero.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.