题解 | #最长递增子序列#

最长递增子序列

http://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481

动态规划二分优化
时间复杂度

arr[]向右偏移为下标从1开始的a[]
g[i]为长度为i的最长上升子序列的最小的末尾元素的下标
last[i]表示以第i个元素结束的最长上升子序列的上一个元素的下标

const int N = 100010;
class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */

    int g[N], a[N], last[N];
    vector<int> LIS(vector<int>& arr) {
        memset(g, 0, sizeof g);
        int n = arr.size(), len = 0;

        a[0] = -1;
        for(int i = 1; i <= n; i ++)
        {
            a[i] = arr[i - 1];

            int l = 0, r = len;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(a[i] > a[g[mid]])  l = mid;
                else  r = mid - 1;
            }
            last[i] = g[l];
            g[l + 1] = i;
            if(l + 1 > len)  len ++;

            //for(int i = 1; i <= len; i ++)  printf("%d ", a[g[i]]);  puts("");
        }
        vector<int> res;
        for(int i = g[len]; i; i = last[i])  res.push_back(a[i]);
        reverse(res.begin(), res.end());
        return res;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:10
点赞 评论 收藏
分享
昨天 10:44
青岛工学院 Java
机械打工仔:对方没做错任何事,你自己在这自找没趣呢,就算他工资不高,人家定多少薪资是人家的事,况且人家写了1~3年清清楚楚
点赞 评论 收藏
分享
07-03 16:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务