# My 30/35 NA DP solution and thinking process

• Initially I thought this question was a DP question since it asks for maximum subarray and looks like an optimization problem. So I came up with a O(n^2) DP solution as follows:

``````public int maxSubArrayLen(int[] nums, int k) {
if( nums==null || nums.length<1 ) return 0;
int row = nums.length;
int result = 0;
int[][] dp = new int[row][row];

for( int i=0; i<row; i++ ){
for( int j=0; j<row; j++ ){
if( i==0 && j==0 ){
dp[i][j] = nums[0];
if( dp[i][j] == k ) result = 1;
}
else if(i<=j){
dp[i][j] = dp[i][j-1]+nums[j];
if( dp[i][j] == k ){
if( j-i+1>result ){
result = j-i+1;
}
}
}
}
}
return result;
}
``````

dp[i][j] represents the sum from index i to index j (inclusive). And I maintain a variable "result" to keep track of the maximum subarray size. The state transition for dp is: dp[i][j] = dp[i][j-1]+nums[j] which is pretty straightforward.
Unfortunately, my dp solution was not accepted and only passed 30 tests out of 35. And got a time limit exceeded error for the 31st test.

Then I saw @he17's solution which is really smart. he17's improvement is that there is no need to cache the sum from index i to j. Instead sum from index i to j can be expressed by sum(0,j)-sum(0,i-1). In this way a 2D array can be reduced to 1D. The detailed implementation is shown below:

public int maxSubArrayLen(int[] nums, int k) {

``````    if( nums==null || nums.length<1 ) return 0;
int result = 0;
int sum = 0;
Map<Integer,Integer> map = new HashMap<>();
for( int i=0;i<nums.length; i++ ) {
sum += nums[i];
if( sum == k ) result = i+1;
else if( map.containsKey(sum-k) ) {
result = Math.max(result, i-map.get(sum-k));
}

if( !map.containsKey(sum) ) {
map.put(sum, i);
}
}

return result;
}``````

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