最长递增子序列

记录路径

class Solution {
 public:
  int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n + 1), parent(n + 1);
    int ans = 1, tail = 0;
    for (int i = 0; i < n; ++i) {
      dp[i] = 1;
      parent[i] = i;
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (nums[j] < nums[i]) {
          if (dp[j] + 1 > dp[i]) {
            parent[i] = j;
            dp[i] = dp[j] + 1;
          }
          if (dp[i] > ans) {
            ans = dp[i];
            tail = i;
          }
        }
      }
    }
    vector<int> rec;
    rec.emplace_back(nums[tail]);
    while (parent[tail] != tail) {
      tail = parent[tail];
      rec.emplace_back(nums[tail]);
    }
    reverse(rec.begin(), rec.end());
    for (auto i : rec) {
      cout << i << " ";
    }
    return ans;
  }
};