300. Longest Increasing Subsequence.md

300. Longest Increasing Subsequence

Question

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Thinking:

• Method:
  • DP

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length + 1];
        int res = 1;
        for(int i = 1; i <= nums.length; i++){
            dp[i] = 1;
            int cmp = nums[i - 1];
            for(int j = 0; j < i - 1; j++){
                if(nums[j] < cmp){
                    dp[i] = Math.max(dp[i], dp[j + 1] + 1);
                }
                res = Math.max(dp[i], res);
            }
        }
        return res;
    }
}

Second time

1. Still use dp to solve this question. O(N^2)

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int[] dp = new int[len + 1];
        for(int i = 1; i <= len; i++) dp[i] = 1;
        int result = 1;
        for(int i = 2; i <= len; i++){
            int num = nums[i - 1];
            for(int j = i - 1; j >= 1; j--){
                if(num > nums[j - 1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(dp[i], result);
        }
        return result;
    }
}

Third time

• Method 1: dp O(N^2)

  • dp[i]: the max increasing subarray up to current index.

   class Solution {
   	public int lengthOfLIS(int[] nums) {
   		int len = nums.length;
   		if(len == 0) return 0;
   		int[] dp = new int[len];
   		Arrays.fill(dp, 1);
   		int max = 1;
   		for(int i = 1; i < len; i++){
   			for(int j = i; j >= 0; j--){
   				if(nums[i] > nums[j]){
   					dp[i] = Math.max(dp[i], dp[j] + 1);
   				}
   				max = Math.max(max, dp[i]);
   			}
   		}
   		return max;
   	}
   }

• Method 2: BST O(NlgN)

  • we insert the values to tree in order and before inserting a node, we need to update the values.

   class Solution {
   	private static class Node{
   		int val, count;
   		Node left, right;
   		public Node(int val, int count){
   			this.val = val;
   			this.count = count;
   		}
   	}
   	private Node root;
   	private int search(Node node, int val){
   		if(node == null) return 0;
   		int count = node.count;
   		int leftMax = 0, rightMax = 0;
   		if(val == node.val){
   			return search(node.left, val);
   		}else if(val < node.val){ // current node is at left side
   			return search(node.left, val);
   		}else{  // val > node.val
   			leftMax = search(node.left, val);
   			rightMax = search(node.right, val);
   			return Math.max(count, Math.max(leftMax, rightMax));
   		}
   	}
   	private void insert(Node node, int val, int count){
   		int cur = node.val;
   		if(cur == val){
   			node.count = count;   
   		}else if(cur < val){
   			if(node.right == null) node.right = new Node(val, count);
   			else insert(node.right, val, count);
   		}else{
   			if(node.left == null) node.left = new Node(val, count);
   			else insert(node.left, val, count);
   		}
   	}
   	public int lengthOfLIS(int[] nums) {
   		int len = nums.length;
   		if(len == 0) return 0;
   		else if(len == 1) return 1;
   		this.root = new Node(nums[0], 1);
   		int max = 1;
   		for(int i = 1; i < len; i++){
   			int count = search(root, nums[i]) + 1;
   			insert(root, nums[i], count);
   			max = Math.max(max, count);
   		}
   		return max;
   	}
   }