s**x
发帖数: 7506 | | k****r
发帖数: 807 | 2 我写了一个，不知道可用不，先用DP找到最长subsequence的长度，complexity is O(
nlongn);
再用recursive找到所有可行解。
public static List> AllLongestIncreasingSubsequence(int[] nums
) {
int[] m = new int[nums.length + 1];
int L = 0;
for (int i = 0; i < nums.length; i++) {
int lo = 1;
int hi = L;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[m[mid]] < nums[i]) lo = mid + 1;
else hi = mid - 1;
}
int newL = lo;
m[newL] = i;
if (newL > L) {
L = newL;
}
}
List> res = new ArrayList<>();
Helper(nums, L, 0, new ArrayList(), res);
return res;
}
public static void Helper(int[] nums, int len, int index, List tmp,
List> res) {
if (tmp.size() == len) {
res.add(new ArrayList(tmp));
return;
}
for (int i = index; i < nums.length; i++) {
if (tmp.size() == 0 || tmp.get(tmp.size() - 1) < nums[i]) {
tmp.add(nums[i]);
Helper(nums, len, i + 1, tmp, res);
tmp.remove(tmp.size() - 1);
}
}
}
public static void main(String[] args) {
int[] input = {2,7,1,3,10,4,5,6};
int[] res = LongestIncreasingSubsequence(input);
for (int i : res) {
System.out.print(i + ",");
}
int[] input2 = {1,6,2,7,3,8,9,10,4,5};
List> res2 = AllLongestIncreasingSubsequence(input2);
for (List l : res2) {
for (Integer i : l) {
System.out.print(i + ",");
}
System.out.println();
}
} | s**x
发帖数: 7506 | 3
nums
Thanks a million !!
【在 k****r 的大作中提到】
: 我写了一个，不知道可用不，先用DP找到最长subsequence的长度，complexity is O(
: nlongn);
: 再用recursive找到所有可行解。
: public static List> AllLongestIncreasingSubsequence(int[] nums
: ) {
: int[] m = new int[nums.length + 1];
: int L = 0;
: for (int i = 0; i < nums.length; i++) {
: int lo = 1;
: int hi = L;
| a****e
发帖数: 9589 | 4 这个太长了，背不下来。
【在 k****r 的大作中提到】
: 我写了一个，不知道可用不，先用DP找到最长subsequence的长度，complexity is O(
: nlongn);
: 再用recursive找到所有可行解。
: public static List> AllLongestIncreasingSubsequence(int[] nums
: ) {
: int[] m = new int[nums.length + 1];
: int L = 0;
: for (int i = 0; i < nums.length; i++) {
: int lo = 1;
: int hi = L;
| k****r
发帖数: 807 | 5 有个main函数，觉得不能再短了：）
【在 a****e 的大作中提到】
: 这个太长了，背不下来。
|
|
