2019/04/20 14:34

# 题目

输入: [10,9,2,5,3,7,101,18]



# 分析

## 初步分析

a[n]为输入数组的内容
f(n)为前N个元素中最长子序列长度，f(n+1)与f(n)的关系并不明朗


g(n)为以第N个元素结尾的最长上升子序列长度，上述的f(n)=max(g(k)) 0<=k<=n

g(n+1)=max(1,g(k)+1) 条件为(0<=k<=n & a[n+1]>a[k])



a[n] g(n)
5 3
7 3
2 2
1 1

a[n] g(n)
6 4
5 3
7 3
2 2
1 1

a[n] g(n)
6 4
5 3
2 2
1 1

a[n] g(n)
6 4
5 3
3 3
2 2
1 1

a[n] g(n)
6 4
3 3
2 2
1 1

# 代码

public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int fn = 1;
int[] gnArr = new int[nums.length];
gnArr[0] = 1;
for (int i = 1; i < nums.length; i++) {
int max = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
max = Math.max(max, gnArr[j] + 1);
}
}
gnArr[i] = max;
fn = Math.max(fn, max);
}
return fn;
}


public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] d = new int[nums.length];
int pos = 0;
d[pos] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > d[pos]) {
pos++;
d[pos] = nums[i];
} else {
d[binarySearch(d, pos, nums[i])] = nums[i];
}
}
return pos + 1;
}

private int binarySearch(int[] arr, int end, int key) {
int left = 0;
int right = end;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (arr[mid] >= key) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}


0
2 收藏

0 评论
2 收藏
0