//
// Created by 罗炳国 on 2023/11/16.
//

#ifndef PFJ_CODE031_LENGTHOFLIS_H
#define PFJ_CODE031_LENGTHOFLIS_H
#include "commonHeader.h"
/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * https://leetcode.cn/problems/longest-increasing-subsequence/description/
 **/

class code031_lengthOfLIS {
public:
    // O(N2)
    int lengthOfLIS(vector<int>& nums) {
        int N = nums.size(), ans = 0;

        // 必须以nums[i]结尾的字串，最长递增子序列是多长
        vector<int> dp(N, 0);

        for (int i = 0; i < N; i++) {
            int maxVal = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    maxVal = max(dp[j], maxVal);
            }
            dp[i] = maxVal + 1;
            ans = max(ans, dp[i]);
        }
        return ans;
    }

    // NlgN
    int lengthOfLISPlus(vector<int>& nums) {

        int N = nums.size();

        //ends[i]表示长度为i+1的最长子序列存在，且当前形成i+1长度的子序列中最小以ends[i]结尾
        vector<int> ends(N, 0);

        for (int i = 0; i < N; i++) {

        }

    }
};


#endif//PFJ_CODE031_LENGTHOFLIS_H