1 子序列 是不要求连续的

2 子数组和子串一样，是需要连续的

300. 最长递增子序列

难度中等1485
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：

  • 1 <= nums.length <= 2500

  • -10 <= nums[i] <= 10


    进阶：

  • 你可以设计时间复杂度为 O(n) 的解决方案吗？

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

    dp解决 这里还要和dp[i]比较，其实是和往前其他满足条件的序列比较

  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         int n = nums.size();
  5.         if(!n) return 0;
  6.         vector<int> dp(n, 0);
  7.         for(int i = 1; i < n; ++ i){
  8.             for(int j = 0; j < i; ++ j){
  9.                 if(nums[i] > nums[j]){
  10.                     dp[i] = max(dp[i], dp[j] + 1);
  11.                 }
  12.             }
  13.         }
  14.         return *max_element(dp.begin(), dp.end());
  15.     }
  16. };

1143. 最长公共子序列

难度中等458
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。


提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。
    1. class Solution {
    2. public:
    3.   int longestCommonSubsequence(string text1, string text2) {
    4.       int n = text1.size(), m = text2.size();
    5.       if(!n || !m) return 0;
    6.       vector<vector<int> > dp(n + 1, vector<int> (m + 1, 0));
    7.       for(int i = 1; i <= n; ++ i){
    8.           for(int j = 1; j <= m; ++ j){
    9.               if(text1[i - 1] == text2[j - 1]){
    10.                   dp[i][j] = dp[i - 1][j - 1] + 1;
    11.               }else{
    12.                   dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    13.               }
    14.           }
    15.       }
    16.       return dp[n][m];
    17.   }
    18. };

    5. 最长回文子串

    难度中等3458
    给你一个字符串 s，找到 s 中最长的回文子串。

    示例 1：
    输入：s = “babad”
    输出：“bab”
    解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

示例 3：
输入：s = “a”
输出：“a”

示例 4：
输入：s = “ac”
输出：“a”


提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成
    1. class Solution {
    2. public:
    3.   string longestPalindrome(string s) {
    4.       int n = s.size();
    5.       if(n == 1)return s;
    6.       string ans;
    7.       vector<vector<int> > dp(n, vector<int>(n));
    8.       for(int l = 0; l < n; ++ l){
    9.           for(int i = 0; i + l < n; ++ i){
    10.               int j = i + l;
    11.               if(l == 0){
    12.                   dp[i][j] = 1;
    13.               }else if(l == 1){
    14.                   dp[i][j] = s[i] == s[j];
    15.               }else{
    16.                   dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
    17.               }
    18.               if(dp[i][j] && l + 1 > ans.size()){
    19.                   ans = s.substr(i, l + 1);
    20.               }
    21.           }
    22.       }
    23.       return ans;
    24.   }
    25. };