题目描述:
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入:[10,9,2,5,3,7,101,18]
输出: 4 解释: 最长的上升子序列是[2,3,7,101],
它的长度是4
。
code:
public class Solution { public int lengthOfLIS(int[] nums) { if (null == nums || 0 == nums.length) { return 0; } if (1 == nums.length) { return 1; } int[] temp = new int[nums.length]; temp[0] = nums[0]; int result = 0; for (int i = 1; i < nums.length; i++) { int l = 0; int r = result + 1; int n = 0; while (l < r) { int mid = (l + r) / 2; if (temp[mid] < nums[i]) { l = mid + 1; } else { r = mid; } } temp[l] = nums[i]; if (l == result + 1) { result++; } } return ++result; } }