题解 | #最长上升子序列(一)#

动态规划：将大问题转化为小问题，每次求解小问题的最优解，再从最优解中挑选出最符合的

#include <algorithm>
#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
  
  int count, length = 0;
  
  std::cin >> count;
  
  std::vector<int> arr(count);
  std::vector<int> dp(count, 1);
  
  for (int i = 0; i < count; i++) {
    std::cin >> arr[i];
  }
  
  for (int i = 0; i < count; ++i) {  // 从小序列到大序列
    for (int j = 0; j < i; ++j) {
      if (arr[i] > arr[j]) {
        dp[i] = std::max(dp[i], dp[j] + 1);  // 子问题的最优解
      }
    }
    length = std::max(length, dp[i]);
  }
  
  std::cout << length << std::endl;
  
  return 0;
}