My concise O(n) DP JAVA Solution


  • 20

    Explanation

    Although there're some other simplified solutions, but DP solution can make the original thought for this problem clearer. In this solution, dp[i] means the largest sum among the subarrays whose last element is A[i].

    Solution1. DP Solution - O(n) time, O(n) space

    public int maxSubArray(int[] A) {
    	int dp[] = new int[A.length]; int max = A[0]; dp[0] = A[0]; 
    	for (int i = 1; i < A.length; i++) {			
    		dp[i] = Math.max(dp[i-1] + A[i] ,A[i]);
    		max = Math.max(max, dp[i]);
    	}
    	return max;
    }
    

    Solution2. Simplified DP Solution - O(n) time, O(1) space - Special thanks for TWiStErRob's smart comment

    The basic idea is to check previous sum, reset it to 0 if it's less than 0.

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

    Solution3. Pre-Sum Array Solution - O(n) time, O(n) space

    The basic idea is to use pre-sum array, max = Math.max(max, sum[i] - minSum). (minSum is the minimum sum before A[i])

    public int maxSubArray(int[] A) {
    	if (A == null || A.length == 0) return 0;
    	int max = A[0], minSum = Integer.MAX_VALUE;
    	int sum[] = new int[A.length];
    	sum[0] = A[0];	
    	for (int i = 1; i < A.length; i++) {
    		sum[i] = sum[i-1] + A[i];
    		minSum = Math.min(0, Math.min(minSum, sum[i-1]));
    		max = Math.max(max, sum[i] - minSum); 
    	}
    	return max;
    }

  • 1
    T

    Removed the array, still DP, still reads the same, but O(1) space:

    public int maxSubArray(int[] A) {
        int max = A[0], dp_i_minus_1 = A[0];
        for (int i = 1; i < A.length; i++) {            
            int dp_i = Math.max(dp_i_minus_1 + A[i] ,A[i]);
            max = Math.max(max, dp_i);
            dp_i_minus_1 = dp_i; // prepare for next iteration
        }
        return max;
    }

  • 0
    J

    Even shorter:

    public int maxSubArray(int[] A) {
        int max = A[0], dp = A[0];
        for (int i = 1; i < A.length; i++) {            
            dp = Math.max(dp + A[i] ,A[i]);
            max = Math.max(max, dp);
        }
        return max;
    }

  • 0
    T

    Huh, that's right. I wanted to make it a point that it reads the same (out loud), but that's really the next potential step. Thanks for sharing!


Log in to reply
 

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