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 is4.
Note:
Follow up: Could you improve it to O(n log n) time complexity?
最长上升子序列。题目就是题意。注意子序列和子串的不同，子序列是可以断开的，只要相对顺序是上升的即可。这个题有两种做法，一是动态规划，一是动态规划基础上的二分。
首先是动态规划。设dp[i]是以nums[i]为结尾的子序列的最大长度。首先初始化的时候，dp数组的每一个元素都是1，因为如果以当前元素为结尾，不看其他元素的话，子序列最大长度就是1。
更新DP数组的方法是用双指针，用一个指针i去遍历input的时候，同时设置另一个指针j扫描j - i的范围，如果在j - i的范围中有数字nums[j] < nums[i]，则dp[i] = Math.max(dp[i], dp[j] + 1)
最后要找的结果是DP数组中的最大值。动图帮助理解。
时间O(n^2)
空间O(n)
Java实现
1 class Solution { 2 public int lengthOfLIS(int[] nums) { 3 // corner case 4 if (nums == null || nums.length == 0) { 5 return 0; 6 } 7 8 // normal case 9 int[] dp = new int[nums.length]; 10 for (int i = 0; i < dp.length; i++) { 11 dp[i] = 1; 12 } 13 for (int i = 0; i < nums.length; i++) { 14 for (int j = 0; j < i; j++) { 15 if (nums[i] > nums[j]) { 16 dp[i] = Math.max(dp[i], dp[j] + 1); 17 } 18 } 19 } 20 int res = 0; 21 for (int i = 0; i < dp.length; i++) { 22 res = Math.max(res, dp[i]); 23 } 24 return res; 25 } 26 }
DP基础上的二分法。创建一个和input等长的input数组，这里的DP数组记录的是实打实的数字，注意最后DP数组中的结果可能并不一定是一个正确的子序列，但是长度是对的。
遍历input，
如果遇到的数字比DP数组里面最大的数字还要大，就加到DP数组的末端；
如果遇到的数字较小，则需要将这个数字通过二分法的方式放到DP数组中他该存在的位置；
时间O(nlogn)
空间O(n)
Java实现
1 class Solution { 2 public int lengthOfLIS(int[] nums) { 3 // corner case 4 if (nums == null || nums.length == 0) { 5 return 0; 6 } 7 8 // normal case 9 int[] dp = new int[nums.length]; 10 dp[0] = nums[0]; 11 int len = 0; 12 for (int i = 1; i < nums.length; i++) { 13 int pos = binarySearch(dp, len, nums[i]); 14 if (nums[i] < dp[pos]) { 15 dp[pos] = nums[i]; 16 } 17 if (pos > len) { 18 len = pos; 19 dp[len] = nums[i]; 20 } 21 } 22 return len + 1; 23 } 24 25 private int binarySearch(int[] dp, int len, int val) { 26 int left = 0; 27 int right = len; 28 while (left + 1 < right) { 29 int mid = left + (right - left) / 2; 30 if (dp[mid] == val) { 31 return mid; 32 } else { 33 if (dp[mid] < val) { 34 left = mid; 35 } else { 36 right = mid; 37 } 38 } 39 } 40 if (dp[right] < val) { 41 return len + 1; 42 } else if (dp[left] >= val) { 43 return left; 44 } else { 45 return right; 46 } 47 } 48 }
[LeetCode] 300. Longest Increasing Subsequence
原文：https://www.cnblogs.com/cnoodle/p/13053361.html