[LeetCode] Longest Increasing Subsequence

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?

思路1：动态规划O(n2)。i为递增子序列的末尾元素的位置，依次遍历i之前的位置，更新其值。
思路2：动态规划+二分搜索O(nlgn)。用一个附加数组保存递增序列的尾元素，依次遍历原数组中的元素，将其插入到附加数组中的正确位置，若插入最后一个元素之后，则更新最长递增子序列的长度。

C++动态规划法实现代码如下:

// Runtime: 132ms

class Solution {

public:

 int lengthOfLIS(vector int nums) {

 if (nums.size() == 0)

 return 0;

 vector int cnt(nums.size(), 1);

 int res = 1;

 for (int i = 1; i nums.size(); i++)

 for (int j = 0; j j++)

 if (nums[j] nums[i] cnt[j] + 1 cnt[i])

 cnt[i] = cnt[j] + 1;

 res = max(res, cnt[i]);

 return res;

};

C++动态规划+二分法实现代码：

// Runtime: 4ms

class Solution {

public:

 int lengthOfLIS(vector int nums) {

 if (nums.size() == 0)

 return 0;

 vector int tail(nums.size(), 0);

 tail[0] = nums[0];

 int len = 1;

 for (int i = 1; i nums.size(); i++)

 int left = 0;

 int right = len - 1;

 while (left = right)

 int mid = (left + right) / 2;

 if (tail[mid] nums[i])

 left = mid + 1;

 else

 right = mid - 1;

 tail[left] = nums[i];

 if (left = len)

 len++;

 return len;

};

java实现代码：

LeetCode 334. Increasing Triplet Subsequence 给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。 数学表达式如下: 如果存在这样的 i, j, k, 且满足 0 i j k n-1， 使得 arr[i] arr[j] arr[k] ，返回 true ; 否则返回 false 。
LeetCode 329. Longest Increasing Path in a Matrix 给定一个整数矩阵，找出最长递增路径的长度。 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
LeetCode 409. Longest Palindrome 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 在构造过程中，请注意区分大小写。比如 Aa 不能当做一个回文字符串。