Longest Increasing Subsequence

This No.300 in LeetCode.

Here are two approaches for this problem, I will introduce both of them here.

Dynamic Programming – O(n^2)

The first solution using Dynamic Programming. We will create a one-dimension dp array. We will go over the whole array, and store the numbers of greater number in dp array.

class Solution {
    public int lengthOfLIS(int[] nums) {

        int dp[] = new int[nums.length];
        Arrays.fill(dp, 1);

        int res = 0;

        for( int i = 0; i < nums.length; i++ ){         
            System.out.println("i is: " + i);
            for( int j = 0; j < i; j++ ){
                System.out.println("j is: " + j);
                if (nums[i] > nums[j]) {
                    System.out.println("nums[i]& nums[j]: " + nums[i] + ", " + nums[j]);
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    System.out.println("Current dp is: " + dp[i]);
                }
            }

            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

Binary Search – O(nlgn)

The second solution using Binary Search. We will create a array with the first element in nums, and then we will go over the whole array, if the new array is greater the last element in array then we insert it, if it is smaller then the first one, then replace the first one. Otherwise, use binary search to find the first element which is not smaller than the new element and then replace it.

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