求Longest_Increasing_Subsequence JAVA O(nlgn) 代码# JobHunting - 待字闺中
m*k
1 楼
m*g
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不好，自己可以修改
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
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 呢？
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
4 楼
每次cached的时候把整个序列都cache下来，最后print out那个最长的序列
m*k
5 楼
刚在collabedit上被问到这道题，干脆就直接拷贝了，面试官，一国人兄弟说他看到过
这段ｃｏｄｅ，
既然这样，我也不需隐瞒，直接告诉他就是我发帖要的ｃｏｄｅ，再装没见过就太掩耳
盗铃了，呵呵。
看来国人兄弟也是有意放水，谢过了哈！
这段ｃｏｄｅ，
既然这样，我也不需隐瞒，直接告诉他就是我发帖要的ｃｏｄｅ，再装没见过就太掩耳
盗铃了，呵呵。
看来国人兄弟也是有意放水，谢过了哈！
相关阅读
再发一个Amazon AWS 工作Use JSON or XML (转载)一般manager都会知道H1B的事情吗？请问airbnb，linkedin rsu fresh问题H1B被revoke后2周新雇主h1b申请说到斗老印如果你有合同工工作想找公司办H1B面试过了，要reference，都会问啥？实现find的功能求data visualization的referstartup的工作值得去吗？朋友h1b被雷 有什么好办法 急急急5/7九章算法班组团只能说， 马工还是很惨的一个行业Contract申请新的opt extensionFacebook内推很大的公司被更大的公司收购g家adwords express未来发展如何？一个朋友double报销面试cost，黑名单了请问各位大牛airbnb的网络工程师工作好申请吗？