题解 | 最长上升子序列(一)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        //动态规划思路一：1，状态定义：dp[i]表示以arr[i]作为结尾的LIS的长度
        //2，状态转移：arr[i]显然要添加到前面已存在的LIS的末尾然后使得长度加一，
        //3，转移方程：dp[i]=max(dp[j])+1,其中j<i,并且arr[j]<arr[i]
        //4，边界条件：dp数组全部初始化为1，因为每个元素自身就是长度一的LIS
        //时间复杂度O（n^2）,空间复杂度O（n）
        // int size=arr.size();
        // if(size==0)
        //     return 0;
        // vector<int>dp(size,1);
        // //遍历arr数组
        // for(int i =0; i<size; i++)
        // {
        //     //遍历dp数组
        //     for(int j=0; j<i; j++)
        //     {
        //         if(arr[j]<arr[i])
        //             dp[i]=max(dp[j]+1,dp[i]);
        //     }
        // }
        // //algorithm中内置找最大值的函数，返回指向最大值的容器
        // auto it=max_element(dp.begin(),dp.end());
        // return *it;

        //思路二：二分查找+贪心 
		//1，状态定义：dp[i]代表所有长度为i+1的LIS中末位元素的最小值
        //2，状态转移：初始dp为空，依次遍历arr中的元素，找到dp中第一个大于等于arr[i]的位置将其更新为arr[i]，如果均小于则将dp长度加一然后把arr[i]添加到dp末尾。
        //解释：dp数组必然是严格上升，可以反证法证明。每个arr[i]也只能更新dp中的一个位置，因为更新多个位置则dp中出现相同元素就不满足严格上升。在我们遍历到arr[i]时，理论上它可以更新dp中第一个大于等于arr[i]以及之前的所有位置，但要满足dp是最小末尾的条件我们只能更新最后一个位置。
        vector<int>dp;
        int size=arr.size();
        //遍历arr
        for(int i=0; i<size; i++)
        {
            //找到dp中第一个大于等于arr[i]的位置（lower_bound找到第一个大于等于的位置，upper_bound找到第一个大于的位置）
            auto it =lower_bound(dp.begin(),dp.end(),arr[i]);
            //如果找到
            if(it!=dp.end())
                *it=arr[i];
            //没找到
            else
            {
                dp.push_back(arr[i]);
            }
        }
        //最后返回dp数组的长度即可
        return dp.size();
    }
};