Time Cost

12min41s

Implementation

dp[i] represents the longest increasing subsequence ends at index. At the end, get the maximum value in dp.

Code

• My Solution

  class Solution {
  public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
  
        for (int i=1; i<nums.size(); i++) {
            for (int j=0; j<i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
          
        return *std::max_element(dp.begin(), dp.end());
    }
  };