经典dp问题
首先是O(n2) 解法
定义dp[i] 为以数组第i个元素为结尾的最长上升子序列的长度，每个位置初始值为1。
对于每个元素i，遍历其之前元素0<= j < i, 若a[i] > a[j], 则a[i]可以作为以a[j]结尾的最长上升子序列的延续
1 public int lengthOfLIS(int[] nums) { 2 if (nums == null || nums.length == 0) { 3 return 0; 4 } 5 int[] dp = new int[nums.length]; 6 Arrays.fill(dp, 1); 7 for (int i = 1; i < nums.length; i++) { 8 for (int j = 0; j < i; j++) { 9 if (nums[i] > nums[j]) { 10 dp[i] = Math.max(dp[i], dp[j] + 1); 11 } 12 } 13 } 14 int result = 0; 15 for (int i = 0; i < nums.length; i++) { 16 result = Math.max(result, dp[i]); 17 } 18 return result; 19 }
follow up: O(nlgn) 解法
dp[i] 表示长度为i的上升子序列中的最大值， 初始值为无穷大，表示不存在长度为i的上升子序列
对于数组中每个元素a[i]，找到dp数组中a[i]对应的lowerbound（二分查找）更新dp[i]的值，使同长度的上升序列的最大值尽可能小
最后遍历dp[i]，找到最大的i且值不为无穷大
1 public class Solution { 2 public int lengthOfLIS(int[] nums) { 3 if (nums == null || nums.length == 0) { 4 return 0; 5 } 6 int[] dp = new int[nums.length]; 7 Arrays.fill(dp, Integer.MAX_VALUE); 8 for (int i = 0; i < nums.length; i++) { 9 int idx = lowerbound(dp, nums[i]); 10 dp[idx] = nums[i]; 11 } 12 int result = 0; 13 for (int i = 0; i < nums.length; i++) { 14 if (dp[i] != Integer.MAX_VALUE) { 15 result = i + 1; 16 } 17 } 18 return result; 19 } 20 21 private int lowerbound(int[] a, int target) { 22 int result = 0; 23 int begin = 0; 24 int end = a.length - 1; 25 while (begin <= end) { 26 int mid = begin + (end - begin) / 2; 27 if (a[mid] >= target) { 28 result = mid; 29 end = mid - 1; 30 } else { 31 begin = mid + 1; 32 } 33 } 34 return result; 35 } 36 }
geeks上提供了另外一种角度的分析，本质上是一样的
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
第十一篇 Longest Increasing Subsequence
原文：http://www.cnblogs.com/ilovenaomi/p/5150152.html