O(n) Java solution


  • 59
    A

    The catch here is that we have to take care of negative value.
    The solution does 1 iteration with constant space and no DP.

    public class Solution {
    public int maxSubArray(int[] A) {
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < A.length; i++) {
            if (sum < 0) 
                sum = A[i];
            else 
                sum += A[i];
            if (sum > max)
                max = sum;
        }
        return max;
    }
    

    }


  • 0
    This post is deleted!

  • 0
    N

    Could you please explain how did you reach this logic?

    My logic was to find the largest element, and from there find the sums along the left and right of the element...


  • 0
    C

    Great solution, faster than DP as well. You can simplify it a little bit more:

       public int maxSubArray(int[] nums) {
           int sum = 0, max = Integer.MIN_VALUE;
           for(int i = 0; i < nums.length; i++) {
               sum = sum < 0? nums[i] : (sum + nums[i]);
               max = Math.max(sum, max);
           }
           return max;
       }
    

Log in to reply
 

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