O(n) Java Solution


  • 4
    M

    Here is my solution. Basically I keep track of the max sum found and the current ongoing sum. Anytime that the next value is greater than the ongoing sum (including the next value), reset the current sum to be the next value.

    public class Solution {
    public int maxSubArray(int[] A) {
        
    	if (A == null)
    	{
    		return 0;
    	}
    	
    	int maxSum = A[0];
    	int currentSum = A[0];
    	
    	for (int i = 1; i < A.length; i++)
    	{
    		currentSum += A[i];
    		
    		// restart sum if the current value is greater than sum of current + previous
    		if (A[i] > currentSum)
    		{
    			currentSum = A[i];
    		}
    		
    		if (currentSum > maxSum)
    		{
    			maxSum = currentSum;
    		}
    	}
    	
    	return maxSum;
    }
    

    }


Log in to reply
 

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