[C++] Typical DP N^2 solution and NLogN solution from GeekForGeek


  • 43
    M

    This is a classic problem and here is a DP solution for reference
    Please note a NLogN solution can be found in the following link
    Geek for Geek

    class Solution {
    public:
        // There's a typical DP solution with O(N^2) Time and O(N) space 
        // DP[i] means the result ends at i
        // So for dp[i], dp[i] is max(dp[j]+1), for all j < i and nums[j] < nums[i]
        int lengthOfLIS(vector<int>& nums) {
            const int size = nums.size();
            if (size == 0) { return 0; } 
            vector<int> dp(size, 1);
            int res = 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);
                    }
                }
                res = max (res, dp[i]);
            }
            return res;
        }
    };
    

  • 11
    M

    Also a C++ code base on geek for geek.

    // NLogN solution from geek for geek
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) { return 0; } 
        vector<int> tail;  // keep tail value of each possible len
        tail.push_back(nums[0]);
        for (auto n : nums) {
            if (n <= tail[0]) {
                tail[0] = n;
            } else if (n > tail.back()) { // large than the tail of current largest len 
                tail.push_back(n);
            } else {  // find smallest one which is >= n
                int left = 0; 
                int right = tail.size()-1;
                int res = left;
                while(left <= right) {
                    int mid = left + (right-left)/2;
                    if (tail[mid] >= n) {
                        res = mid;
                        right = mid-1;
                    } else { // tail[mid] < n
                        left = mid+1;
                    }
                }
                tail[res] = n;
            }
        }
        return tail.size();
    }

  • 0

    Thank you very much for your nice solution. I am always lost when come to DP problems.


  • 0

    Haha, I feared DP too in the past. Finally I found that once you got the DP formula, coding DP is just translation :-)


  • 0
    L

    me too... wondering is there any good practices (easy to hard) for us who is weak at DP problems.


  • 0
    L

    Yup. but the hard thing is to work out that formula...


  • 3

    Really cool algorithm. In fact, the implementation of the binary search part can still be optimized a bit: using left < right as the terminating condition, we can get rid of res :-)

    The code is as follows.

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            if (nums.empty()) return 0;
            vector<int> ends{nums[0]};
            for (int num : nums) {
                if (num > ends.back()) ends.push_back(num);
                else {
                    int l = 0, r = ends.size() - 1;
                    while (l < r) {
                        int m = l + (r - l) / 2;
                        if (ends[m] < num) l = m + 1;
                        else r = m;
                    }
                    ends[r] = num;
                }
            }
            return ends.size();
        }
    };
    

    There is a more clever implementation using lower_bound in this post, just 6-lines indeed.


  • 0

    @LeoShi Would you like to have a look at here :-)


  • 0

    Hey, your code is really cool, even come to details. Only record the last number of each array instead of whole array, use binary search in else case.


  • 0
    S

    @jianchao.li.fighter u got pretty good understanding


  • 0
    C

    @jianchao.li.fighter, the first if check if (num < ends[0]) ends[0] = num; can be merged into the else check, right?


  • 0

    @caikehe Yeah, you're right! Thanks for your nice suggestions. I have updated my code now :-)


Log in to reply
 

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