算法模板之最长递增子序列(LIS)

暴力法：将所有的排列组合枚举，计算最长的长度，时间复杂度：O(n!)，不可行！

法二：将原序列A复制并升序得到A'，求A 和A'最长公共子序列的长度，即为所求，时间复杂度是O(n^2)

下面介绍另外的两种方法：

模板代码

/**
 * 转移状态： dp[i] = max{0,dp[j]} + 1, 0 < j < i
 * O(n^2)
 * @param nums
 * @return
 */
public int LISByDp(int[] nums) {
    int maxLen = 1, largerLen = 0;
    int[] dp = new int[nums.length];
    dp[0] = 1;
    for (int i = 1; i < nums.length; i++) {
        largerLen = 0;
        for (int j = 0; j < i; j++) {
            if (dp[j] > largerLen && nums[j] < nums[i]) {
                largerLen = dp[j];
            }
        }
        dp[i] = largerLen + 1;
        maxLen = maxLen > dp[i] ? maxLen : dp[i];
    }
    return maxLen;
}

/**
 * O(nlogn)
 * @param nums
 * @return
 */
public int LISByD(int[] nums) {
    int lastIndex = 0;
    int[] d = new int[nums.length];
    d[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > d[lastIndex]) {
            d[++lastIndex] = nums[i];
        } else {
            int j = lower_bound(d, 0, lastIndex, nums[i]);
            d[j] = nums[i];
        }
    }
    return lastIndex + 1;
}

int lower_bound(int[] d, int start, int end, int target) {
    int mid = 0;
    while (start < end) {
        mid = (start + end) / 2;
        if (target > d[mid]) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return end;
}