[C++] 5 Solutions


  • 0
    class Solution {
    public:
        int lengthOfLIS(vector<int> &nums) {
            return method5(nums); // or other methods
        }
    private:
        //-------------------------------------------------------
        // Brute-force, recursive => O(2^n)-time
        int method1(vector<int> &nums) { // TLE
            return helper1(nums);
        }
        int helper1(vector<int> nums) {
            int n = nums.size();
            if (n <= 0) return n;
            int x = nums[n-1];
            nums.pop_back();
            vector<int> remain;
            for (int i = 0; i < n-1; i++)
                if (nums[i] < x) remain.push_back(nums[i]);
            return max(1 + helper1(remain), helper1(nums));
        }
        //-------------------------------------------------------    
        // Brute-force, recursive => (Better than Method1) O(2^n)-time
        int method2(vector<int> &nums) { // TLE
            return helper2(nums, INT_MIN, 0);
        }
        int helper2(vector<int> &nums, int lo, int pos) {
            if (pos >= nums.size()) return 0;
            int x = 0; // length in which nums[pos] is chosen
            if (nums[pos] > lo) 
                x = 1 + helper2(nums, nums[pos], pos + 1); 
            int y = helper2(nums, lo, pos + 1); // length in which nums[pos] is NOT chosen
            return max(x, y);
        }
        //-------------------------------------------------------        
        // Dynamic Programming (top-down, recursive (method2) + memoization)
        // O(n^2) time and space
        int method3(vector<int> &nums) { // MLE
            int n = nums.size();
            nums.push_back(INT_MIN);
            vector<vector<int>> memo (n + 1, vector<int>(n, -1));
            return helper3(nums, n, 0, memo);
        }
        int helper3(vector<int> &nums, int loIndex, int pos, vector<vector<int>> &memo) {
            if (pos >= nums.size() - 1) return 0;
            if (memo[loIndex][pos] != -1) return memo[loIndex][pos];
            int x = 0;
            if (nums[pos] > nums[loIndex])
                x = 1 + helper3(nums, pos, pos + 1, memo);
            int y = helper3(nums, loIndex, pos + 1, memo);
            return memo[loIndex][pos] = max(x, y);
        }
    //-------------------------------------------------------        
        // Dynamic Programming (Iterative)
        int method4(vector<int> &nums) { // O(n^2) time and O(n)-space
            int n = nums.size();
            vector<int> dp (n, 1);
            // dp[i] = length of longest increasing subsequence possible considering the array elements upto the i-th
            //         index only, by necessarily including the i-th element.
            int result = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++)
                    if (nums[i] > nums[j])
                        dp[i] = max(dp[i], 1 + dp[j]);
                result = max(result, dp[i]);
            }
            return result;
        }
    
    //-------------------------------------------------------        
        // Dynamic Programming (Iterative) --> BEST ONE!
        int method5(vector<int> &nums) { // O(nlgn) time and O(n)-space
            int n = nums.size();
            vector<int> dp (n); // dp[i] = last number (biggest number) in an LIS with length i + 1
            int lastIndex = -1; 
            for (int num : nums) {
                int i = BinarySearch(num, 0, lastIndex, dp); // search dp from 0 to lastIndex (inclusive)
                dp[i] = num;
                lastIndex = max(lastIndex, i);
            }
            return lastIndex + 1;
        }
        int BinarySearch(int val, int start, int end, vector<int> &dp) {
            if (start > end) return start;
            int mid = (start + end) / 2;
            if (val == dp[mid]) return mid;
            if (val < dp[mid]) return BinarySearch(val, start, mid - 1, dp);
            return BinarySearch(val, mid + 1, end, dp);
        }
    };
    

Log in to reply
 

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