[How to from Error to AC to Better]thoughts and extensions with C++ implementation


  • 2
    1. Have you ever think how to construct the min-length LIS in O(NlogN) complexity ? [refer related the answer post]

    This is my first implementation, just the largest rectangle in histograms.

    It pass 19/22 cases.

    Here is the failed case:

      [1,3,6,7,9,4,10,5,6]    it returns :  5     correct answer : 6
    

    It fails when meet 4, if not poped, then the longest will be added 10.

    The reason is that , my implementation can not deal with this special case.

    So how to change the code to pass all the cases ? See the answers .

    Original Code:

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int len=nums.size();
            if(len==0) return 0;
            stack<int> ss;
            int result=0;
            for(int i=0; i<len; i++){
                if(ss.empty() || ss.top()<nums[i]){
                    ss.push(nums[i]);
                }
                else{
                    while(!ss.empty() && ss.top()>=nums[i]){
                        ss.pop();
                    }
                    ss.push(nums[i]);
                }
                int cur=ss.size();
                result=max(result, cur);
            }
            return result;
        }
    };

  • 0

    To solve the un-passed cases. I referred to the Geek4Geek

    Refer to the post

    “end element of smaller list is smaller than end elements of larger lists“.

    http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

    I do not think all the posters really understand the intuition behind this elegant solution !

    IT is inspired from here

    Our observation is, assume that the end element of largest sequence is E. We can add (replace) current element A[i] to the existing sequence if there is an element A[j] (j > i) such that E < A[i] < A[j] or (E > A[i] < A[j] – for replace). In the above example, E = 11, A[i] = 8 and A[j] = 9.

    In fact the array we record is a sequence of head element of many LIS sequences. So It can contains the max-length

    In summary

    Querying length of longest is fairly easy. Note that we are dealing with end elements only. We need not to maintain all the lists. We can store the end elements in an array. Discarding operation can be simulated with replacement, and extending a list is analogous to adding more elements to array.

    Here is my standard & concise implementation

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int len=nums.size();
            if(len==0) return 0;
            vector<int> ss;
            int result=0;
            for(int i=0; i<len; i++){
                if(ss.empty() || ss.back()<nums[i]){
                    ss.push_back(nums[i]);
                }
                else{
                    int index=binarySearch(ss, ss.size(), nums[i]);
                    ss[index]=nums[i];
                }
            }
            return ss.size();
        }
        /** find the first bigger value in the array nums */
        int binarySearch(vector<int>& nums, int size, int target){
            int start=-1, end=size-1, mid=0;
            while(end - start > 1){
                mid = (start+end)/2;
                if(nums[mid]>=target)  end=mid;
                else start=mid;
            }
            return end;
        }
        
    };
    

  • 0

    Here is the DP solution, the key is illustrated in the comments.

    Code:

       class Solution {
        public:
            int lengthOfLIS(vector<int>& nums) {
                /** DP implementation **/
                /**
                 *  dp[i] records the LIS length util the position i
                 *  dp[i]=max{dp[j]+1} for all j<i && nums[j]<nums[i]
                 **/
                const int size=nums.size();
                if(size==0)  return 0;
                vector<int> dp(size, 1);
                int result=1;
                for(int i=1; i<size; i++){
                    for(int j=0; j<i; j++){
                        if(nums[j]<nums[i]){
                            dp[i]=max(dp[i], dp[j]+1);
                        }
                    }
                    result=max(result, dp[i]);
                }
                return result;
            }
        };

  • 0

    Let us to construct the LIS array in O(NlogN) complexity.

    There are some key points

     1, we use index-array(tail) instead a value-array
     2, we use the pre-array to record the pre-index of the current-index
    

    Based on this 2 points.

    Here is a concise implementation, but it can only return only one possible longest length solution.

    How about returning all possible longest solutions ???

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int len=nums.size();
            if(len==0)  return 0;
            /*** tail : record the index of all the possible sequences with min-val tail **/
            /*** pre : record the previous index of the current min-val index **/
            vector<int> tail(len, 0);
            vector<int> pre(len, 0);
            tail[0]=0;
            pre[0]=-1;
            int cur_size=1;
            
            for(int i=1; i<len; i++){
                if(nums[i]<nums[tail[0]]){
                    tail[0]=i;
                }
                else if(nums[i]>nums[tail[cur_size-1]]){
                    pre[i]=tail[cur_size-1];
                    tail[cur_size++]=i;
                }
                else{
                    int pos=binarySearch(nums, tail, cur_size, nums[i]);
                    pre[i]=tail[pos-1];
                    tail[pos]=i;
                }
            }
            for(int i=tail[cur_size-1]; i>=0; i=pre[i]){
                cout<<nums[i]<<" ";
            }
            return cur_size;
        }
        /** find the first bigger value in the array nums */
        int binarySearch(vector<int>& nums, vector<int>& tail, int size, int target){
            int start=-1, end=size-1, mid=0;
            while(end - start > 1){
                mid = (start+end)/2;
                if(nums[tail[mid]]>=target)  end=mid;
                else start=mid;
            }
            return end;
        }
        
    };

  • 0
    2

    I made the mistake that initialize the start = 0, it is wrong !! It should be (start, end], open and closed field combination .....


Log in to reply
 

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