C++算法集锦：动态规划

• 最长上升子序列(一)
• 最长上升子序列(二)

牛客链接：NC163 最长上升子序列(一)

定义长度为n的ans数组，用以保存以arr[i]结尾的最长严格上升子序列的长度。在每次获得最长序列的时候进行比较从而得到最终结果。结果满足复杂度要求。

class Solution {
public:
    
    int LIS(vector& arr) {
        // write code here
        if(arr.size()==0)
            return 0;
        int res = 0;
        vector ans(arr.size(),1);
        for(int i = 1; i < arr.size();++i){
            for(int j =0; j
                if(arr[i]>arr[j])
                    {
                        ans[i] = max(ans[i],ans[j]+1);
                    }
            }
            res = max(ans[i] ,res);
        }
        return res;
    }
};

牛客链接：NC164 最长上升子序列(二)

和上题目目的相同，只是更严格的要求了时间和空间复杂度。这里使用动态规划+二分的思路。
arr[i]用来存储尽可能小的值，因为小的值在后续中，更可能寻找到大的值从而使得长度增加。
遍历每个a[ i ]，如果严格大于arr的最后一个数，则加入arr；
否则，找到找到大于等于他的最小的一个数，进行替换。
最终获得的arr的长度就是答案。

//实现1：手写二分
class Solution {
public:
    
    int LIS(vector& a) {
        // write code here
        int n=a.size();
        if(n==0)
            return 0;
        vector arr;
        arr.push_back(a[0]);
        for(int i =1;i
            if(a[i]>arr.back()){
                arr.push_back(a[i]);
            }
            else{
                int l=0, r = arr.size()-1,mid;
                while(l    	//寻找>=的位置     也可以直接使用lower_bound() 替代
                    mid = (l+r)>>1;
                    if(arr[mid]>=a[i])
                        r = mid;
                    else
                        l = mid+1;
                }
                arr[l] = a[i];  //更新长度为l的子序列的最小值
            }
        }
        return arr.size();
    }
};


//实现2:调用函数
class Solution {
public:
    
    int LIS(vector& a) {
        // write code here
        vector arr;
        for(int i : a){
            vector::iterator it = lower_bound(arr.begin(),arr.end(),i);
            if(it == arr.end())
                arr.push_back(i);
            else
                *it = i;
        }
        return arr.size();
    }
};