最长递增子序列问题---动态规划

参考https://www.cnblogs.com/coffy/p/5878915.html

问题描述

设L=<a1,a2,...an>是n个不同的实数，L的递增子序列是这样一个子序列：Lin=<aK1,aK2,…,aKm>，其中K1<K2<…<Km且aK1<aK2<…<aKm，求最大的m值。

解法1：转化为LCS问题求解

先对L进行排序得到L'，然后计算L'与L的最长公共子序列，显然这个最长公共子序列即为L的最长递增子序列。时间复杂度O(n^2)

解法2：动态规划法

设f(i)表示以第i个元素为末尾元素时的最长递增子序列长度。则递推公式如下：

在求以ai为末元素的最长递增子序列时，找到所有序号在L前面且小于ai的元素aj，即j<i且aj<ai。如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
时间复杂度O(n^2)

int LongestSubArray(vector<int>& arr){
    if(arr.size()<1)
        return -1;

    vector<int> ll(arr.size(), 1);
    
    for(int i=1; i<arr.size(); i++){
        for(int j=0; j<i; j++){
            if(arr[j]<arr[i] && ll[j]>=ll[i])
                ll[i] = ll[j] + 1;
        }
    }
    
    int ret = ll[0];
    for(int i=1; i<ll.size(); i++){
        if(ret<ll[i])
            ret = ll[i];
    }

    return ret;
}

补充一种nlogn解法

bool checkSubarraySum(vector<int>& nums, int k){
    vector<int> dp;
    dp.push_back(nums[0]);
    for(int i=1; i<nums.size(); i++){
        if(nums[i]>dp.back())
            dp.push_back(nums[i]);
        else{
            int aim = lower_bound(dp.begin(), dp.end(), nums[i]);
            dp[aim] = nums[i];
        }
    }
    return dp.size();
}