Description Link to heading

300.longest-increasing-subsequence

Solution Link to heading

The key point is: what dp[i] means is conducive to solving this problem. Since subsequence may be not continuous, dp[i] should denotes maximum length increaing subsequence ending with nums[i - 1];

Recurrence formula:

if (nums[i - 1] > nums[j - 1]) // j < i
    dp[i] = max(dp[j] + 1, dp[i])

Code Link to heading 

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        vector<int> dp(nums.size() + 1, 1); // initialize dp[i] as 1 since there is one element at least
        // dp[1] = 1;
        // int index = 0;
        int m = 0;
        for (int i = 1; i <= nums.size(); i++) {
            for (int j = 1; j < i; j++) {
                if (nums[i - 1] > nums[j - 1])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            if (dp[i] > m)
                m = dp[i];
        }
        return m;
    }
};