请问dp的解法中,dp数组的长度为什么是nums.length+1呢?int[] dp = new int[nums.lengtj +1];
2020-03-26
1
2
mickey
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
List<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < nums.length; i++) {
int lower = binarySearch(list, nums[i]);
if (lower == list.size()) {
list.add(nums[i]);
} else {
list.set(lower, nums[i]);
}
}
return list.size();
}
public static int binarySearch(List<Integer> list, int key) {
int low = 0;
int high = list.size() - 1;
while (high >= low) {
int mid = (low + high) / 2;
if (key <= list.get(mid))
high = mid - 1;
else
low = mid + 1;
}
return low;
}
}