m*****k
发帖数: 731 | | m********g
发帖数: 272 | 2 public static int longestIncreasingSubConsequence(int[] array) {
int length = array.length;
int[] valueAtLength = new int[length];
int maxNow = 1;
valueAtLength[0] = array[0];
for(int i = 1; i < length; i++) {
int updatePos = findPos(valueAtLength, maxNow, array[i]);
if(updatePos == maxNow) {
valueAtLength[maxNow++] = array[i];
} else {
valueAtLength[updatePos] = array[i];
}
}
return maxNow;
}
private static int findPos(int[] array, int length, int target) {
int low = 0;
int high = length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(mid == low) {
if(array[mid] >= target) {
return mid;
} else {
mid = mid + 1;
if(mid > high) {
break;
}
}
}
if(array[mid] >= target && array[mid - 1] < target) {
return mid;
} else if (array[mid] < target) {
low = mid + 1;
} else if(array[mid - 1] >= target) {
high = mid - 1;
}
}
return length;
}
变量的naming不好，自己可以修改 | m*****k
发帖数: 731 | 3 谢谢myanything 大虾，
int[] array= new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7,
15
};
如何输出 0 2 6 9 11 15 呢？ | m********g
发帖数: 272 | 4 每次cached的时候把整个序列都cache下来，最后print out那个最长的序列 | m*****k
发帖数: 731 | 5 刚在collabedit上被问到这道题，干脆就直接拷贝了，面试官，一国人兄弟说他看到过
这段ｃｏｄｅ，
既然这样，我也不需隐瞒，直接告诉他就是我发帖要的ｃｏｄｅ，再装没见过就太掩耳
盗铃了，呵呵。
看来国人兄弟也是有意放水，谢过了哈！ |
|
