O(nlgn) with data structures (Fenwick Tree)


  • 0
    H

    Most O(n lg n) solutions use DP on the length of the LIS, storing the smallest possible last number for each length.

    Another method is instead to use the exact same recurrence as the O(n^2) solution, where dp[i] = max(dp[j] if j<i and nums[j] < nums[i])+1. We can sort the array by increasing number (break ties by decreasing index) and for each number (in sorted order), we query the maximum length subsequence ending before that index. Then, for that index, we put in 1+maximum length ending before that index as the value.

    A Fenwick tree supports both operations (add in a value, get prefix maximum) in O(n lg n) time. It is basically a simplified segment tree.

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            N = nums.size();
            bit = new int[N+1];
            fill(bit, bit+N+1, 0);
            vector<pair<int,int> > p;
            for(int i=0;i<N;i++) {
                p.push_back(make_pair(nums[i], -(i+1)));
            }
            sort(p.begin(), p.end());
            for(int i=0;i<N;i++) {
                add(-p[i].second, get(-p[i].second)+1);
            }
            return get(N);
        }
    private:
        int* bit, N;
        void add(int x, int val) {
            for(; x<=N; x+=x&-x) bit[x] = max(bit[x], val);
        }
        int get(int x) {
            int ret = 0;
            for(; x; x&=(x-1)) ret = max(ret, bit[x]);
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.