Explanation on applying the dynamic programming method for this problem.

• 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;
}``````

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

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