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

最长递增子序列

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;
    }
};
全部评论

相关推荐

醉蟀:你不干有的是人干
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 10:56
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

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