Share Java DP solution


  • 7

    dp[i] represents the the length of the LIS till nums[i].

    For each nums[i], we need to compare all the nums[j] where 0 <= j < i, if nums[i] > nums[j], then dp[i] = dp[j] + 1, that means we have found a potential LIS.

    Let i go through the nums[] array, eventually we will get the longest length of LIS.

    Time complexity is O(n^2).

    public int lengthOfLIS(int[] nums) {
      if (nums.length == 0) return 0;
      
      int n = nums.length, max = 0;
      int[] dp = new int[n];
      
      for (int i = 0; i < n; i++) {
        dp[i] = 1;
        
        for (int j = 0; j < i; j++) {
          if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
            dp[i] = dp[j] + 1;
          }
        }
        
        max = Math.max(max, dp[i]);
      }
      
      return max;
    }

Log in to reply
 

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