O(n) Java solution

  • 55

    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];
                sum += A[i];
            if (sum > max)
                max = sum;
        return max;


  • 0
    This post is deleted!

  • 0

    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...

Log in to reply

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