算法基础之最长上升子序列

最长上升子序列

• 核心思想：线性dp

  • 明确f[N]集合定义 : 以第i个数结尾的最长子序列

  • 计算 : a[j]为 a[i] 前面一个数值 若f [j] + 1 > f [i] 则f [i] = f [j] + 1 所以 f[i] = max(f[i] , f[j] + 1)

  • 

  •   #include<iostream>
      #include<algorithm>
      #include<cstring>
      
      using namespace std;
      const int N = 1010;
      
      int f[N],a[N];
      int n;
      
      int main()
      {
          cin>>n;
          for(int i=1;i<=n;i++) cin>>a[i];  //a存数值
          
          for(int i=1;i<=n;i++)
          {
              f[i] = 1;  //用到i的时候初始化成1 (子序列只有自己)
              for(int j = 1;j<i;j++)  //j<i 遍历i之前所有数
              {
                  if(a[j] < a[i]) f[i] = max(f[i] , f[j] + 1); 
              }
          }
          
          int res = 0;  //遍历所有f[i] 找到最大的
          for(int i=1;i<=n;i++) res = max(res , f[i]);
          
          cout<<res;
      }