300. 最长递增子序列

class Solution {
public:
  int lengthOfLIS(vector<int>& nums) {
    // A sequence has a minimum length of 1.
    vector<int> Length(nums.size(), 1);
    for (int i = 1; i < nums.size(); ++i) {
      for (int j = 0; j < i; ++j) {
        // Current selected value nums[i] is larger than the subsequence ending
        // with nums[j], which means that nums[i] can be added to the tail of
        // the subsequence.
        if (nums[j] < nums[i])
          Length[i] = max(Length[i], Length[j] + 1);
      }
    }
    return *max_element(Length.begin(), Length.end());
  }
};

class Solution {
public:
  int lengthOfLIS(vector<int>& nums) {
    int Result = 1;
    vector<int> DP(nums.size(), 1);
    for (int i = 0; i < nums.size(); ++i) {
      for (int j = i; j >= 0; --j) {
        if (nums[j] < nums[i])
          DP[i] = max(DP[i], DP[j] + 1);
      }
      Result = max(Result, DP[i]);
    }
    return Result;
  }
};