Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

O(n^2)

based on longest common subsequence

转化为最长公共子序列问题。先将数组排序(升序)，然后寻找与原数组的最长公共子序列。该子序列即为最长递增子序列。

e.g.
[10, 9, 2, 5, 3, 7, 101, 18]
[2, 3, 5, 7, 9, 10, 18, 101]

based on dp

用动规思想，分解成子问题。
用dp[i]记录数组第i个元素及之前元素的最长递增子序列长度。
比如，对于输入数组nums[n]，dp[i]记录nums[0] - nums[i]部分的最长递增子序列长度。
怎么获得dp[i]呢？根据dp[j] (j < i)以及nums的值。

若a[i]是递增序列的最后一个元素(大于子序列的所有元素)，则在之前记录的长度上加一。
若a[i]不是最后一个元素(小于输入数组前面所有元素)，则当前最长子序列就是它本身，长度为一。

dp[i] = max(dp[j] + 1), where (j < i) && (nums[j] < nums[i]).
dp[i] = 1, where (j < i) && (nums[j] >= nums[i]).

遍历途中用遍历max记录最大长度。

e.g.
a: [10, 9, 2, 5, 3, 7, 101, 18]
dp:[ 1, 1, 1, 2, 2, 3, 4, 4]

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

O(n log n)

在上一个dp中，对于元素a[i]，需要遍历之前所有的dpj。
用dp[i]表示当最长子序列长度为i时，该子序列最后一位数字。

e.g.
a: [10, 9, 2, 5, 3, 7, 101, 18]
1st. dp[1] = a[0] = 10，当只有第一个数字10时，长度为1的最长子序列的最后一位是10.
2nd. dp[1] = a[1] = 9, 对于第二个数字9，因为它小于原先的dp[1]，所以此时的长度依然为1，将9放入dp[1]。
3rd. dp[1] = a[2] = 2, 同上。
4th. dp[1 + 1] = a[3] = 5，此时5>2，符合递增条件，所以最长子序列长度加一，即长度为2的子序列最后一位是5.
5th. dp[2] = a[4] = 3， 3介于2和5之间，更新5。(每次更新最小的那位大于a[i]的数)
6th. dp[3] = a[5] = 7。
7th. dp[4] = a[6] = 101。
8th. dp[4] = a[7] = 18。
最后，dp = [2, 3, 7, 18]。

在寻找替换位时，因为dp一定是升序数组，所以可以使用二分查找，而不用遍历所有，可以减少复杂度。

public int lengthOfLIS(int[] nums) {
       if (nums.length == 0)
           return 0;
       int max = 1;
       int[] dp = new int[nums.length+1];
       dp[1] = nums[0];
       for (int i = 1; i < nums.length; i++) {
           if (nums[i] > dp[max])
               dp[++max] = nums[i];
           else {
               int left = 1, right = max;
               while (left < right) {
                   int mid = left + (right - left) / 2;
                   if (nums[i] <= dp[mid])
                       right = mid;
                   else 
                       left = mid + 1;
               }
               dp[left] = nums[i];
           }
       }
       return max;
   }