300. 最长递增子序列

【题目】给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
【分析1】找到所有递增子序列，然后求最长长度，超时，通过率：22/54；
【分析2】动态规划，

  1. class Solution {
  2.     LinkedList<LinkedList<Integer> > allLIS = new LinkedList<>();
  3.     public int lengthOfLIS(int[] nums) {
  4.         //找到所有递增子序列，然后返回最长的长度
  5.         LinkedList<Integer> temp = new LinkedList<>();
  6.         dfs(nums, 0, -10001, temp);
  7.         int res = 0;
  8.         for (LinkedList<Integer> lis : allLIS) {
  9.             res = Math.max(res, lis.size());
  10.         }
  11.         return res;
  12.     }
  13.     public void dfs(int[] nums, int cur, int preNum, LinkedList<Integer> temp) {
  14.         if (cur == nums.length) {
  15.             if (!temp.isEmpty()) {
  16.                 allLIS.add(new LinkedList<>(temp));
  17.             }
  18.             return;
  19.         }
  20.         if (nums[cur] > preNum) {
  21.             temp.add(nums[cur]);
  22.             dfs(nums, cur+1, nums[cur], temp);
  23.             temp.removeLast();
  24.         }
  25.         if (nums[cur] != preNum) {
  26.             dfs(nums, cur+1, preNum, temp);
  27.         }
  28.     }
  29. }
class Solution {
    public int lengthOfLIS(int[] nums) {
        //动态规划思路，dp[i]表示以num[i]这个数结尾的最长递增子序列的长度
        int n = nums.length;
        int[] dp = new int[n];
        for (int i=0; i<n; i++) {
            dp[i] = 1;
        }

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