My easy to understand O(n^2) solution using DP with video explanation


  • 57
    S

    This solution is taken from this great guy -
    https://www.youtube.com/watch?v=CE2b_-XfVDk

        public int lengthOfLIS(int[] nums) 
    	{
    		// Base case
    		if(nums.length <= 1) 
    			return nums.length;
    
    		// This will be our array to track longest sequence length
    		int T[] = new int[nums.length];
    
    		// Fill each position with value 1 in the array
    		for(int i=0; i < nums.length; i++)
    			T[i] = 1;
    
    
    		// Mark one pointer at i. For each i, start from j=0.
    		for(int i=1; i < nums.length; i++)
    		{
    			for(int j=0; j < i; j++)
    			{
    				// It means next number contributes to increasing sequence.
    				if(nums[j] < nums[i])
    				{
    					// But increase the value only if it results in a larger value of the sequence than T[i]
    					// It is possible that T[i] already has larger value from some previous j'th iteration
    					if(T[j] + 1 > T[i])
    					{
    						T[i] = T[j] + 1;
    					}
    				}
    			}
    		}
    
    		// Find the maximum length from the array that we just generated 
    		int longest = 0;
    		for(int i=0; i < T.length; i++)
    			longest = Math.max(longest, T[i]);
    
    		return longest;
    	}

  • 0
    W

    Why do I need to fill dp with 1? Can't I just do dp[0] = 1 before the loop?


  • 0
    G

    I think filling dp with 1s can help handle the case when nums[i] is smaller than all nums[j]. You can of course do something to keep track of whether all nums[j] are bigger than nums[i], and when that happens you fill dp[i] with 1, but that seems to be a lot more complicated than filling the whole array with 1s.


  • 0
    J

    this is regular DP question, exactly the same as mine


  • 0

    I think you don't need to fill array T with ones, you just need to plus one when you return the longest.


  • 16
    H
    public static int lengthOfLIS2(int[] nums) {
    		if(nums.length == 0 || nums == null){
                return 0;
            }
            int []dp = new int[nums.length];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[j] < nums[i]) {
                        dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
                    }
                }
                if (dp[i] > max) {
                    max = dp[i];
                }
            }
            return max;
        }

  • 2
    T
    public int lengthOfLIS(int[] nums) {
        if(nums==null || nums.length == 0 ) return 0;
        
        int[] dp = new int[nums.length];
        int max = Integer.MIN_VALUE;
        for( int i=0; i<nums.length; i++ ){
            dp[i] = 1;
            for( int j=0; j<i; j++ ){
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        
        return max;
    }

  • 0
    E

    Thanks for the link to the video.
    The video is very helpful.

    One thing:

    Arrays.fill(T, 1);
    

    which looks concise.


  • 0

    i suppose T[j] would never actually exceed T[i], so if(T[j] == T[i]) shall also good to work instead of if(T[j] + 1 > T[i]).


Log in to reply
 

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