My 30/35 NA DP solution and thinking process


  • 0
    T

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

Log in to reply
 

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