Explanation on applying the dynamic programming method for this problem.


  • 5
    L

    The dynamic programming method to solve this problem relies on the following formulas:

    L[i] = max(L[i-1] + A[i], A[i])
    

    where L[i] stores the maximum sum of continuous subarray starting from the element A[i] towards the end of A[0].

    Note that, the subarray that has the maximum value does not necessarily need to contain the element A[i]. It is just that L[i] holds the value, so that it can be used by the next iteration.

    Once we reach the end of the array with L[i], which is to say that, we obtain the maximum sum of continuous subarray for the entire array.

    public int maxSubArray(int[] A) {
        	if(A.length == 0){
        		return 0;
        	}
        	
        	int [] dp = new int[A.length]; 
            
            int max_sum = 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_sum = Math.max(dp[i], max_sum);
        	}
            
            return max_sum;	 
        }

  • 0
    M

    No need to store an entire array for this solution, only need to save one temp 'lookback' value. You're currently using dp[i-1] for that instead.


Log in to reply
 

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