S*******C
发帖数: 822 | 1 Google面试题
Given a sequence S of integers, a subsequence is any selection of numbers of
S in the same order as S. For example, if S = 1,1,2,3,5,8,13 then 2,3,8 is
a subsequence of S and so is 1,1,5,13 and so is 1,2,3. However, 5,6,7 is not
a subsequence, 8,5,2 is also not a subsequence.
A subsequence T is increasing is T[i] < T[i+1] for all i.
Given a sequence S = 4, 9, 3, 8, 6, 7, 10 .... : we can have 3, 8, 10 or 4,
9, 10 or 4, 6,7,10 as its increasing subsequences.
Our task is : given a sequence S of n numbers, count the number of
increasing subsequences of S. Given an O( n log n) algorithm to accomplish
this task. | S*******C
发帖数: 822 | 2 我这里有一个求最长递增子序列长度的O(nlogn)动态规划算法作为参考
public class LongestIncreasingSubseq {
static int min_last_element[];// 记录长度为i的递增子序列中最大元素的最小
值, min_last_element is an sorted array
static int lengthOfLIS;
public static void main(String args[]) {
int a1[] = new int[] { 12, 11, 13, 10, 14, 11, 15, 12, 17, 20, 11,
22 };
min_last_element= new int[a1.length];
System.out.println(findLongestIncreasingSubseq(a1, a1.length));
}
// 返回min_last_element[i]中刚刚大于x的那个元素的下标
static int binarySearch(int[] min_last_element, int lengthOfLIS, int x) {
int left = 0, right = lengthOfLIS, mid;
while (left <= right) {
mid = (left + right) / 2;
if (x > min_last_element[mid])
left = mid + 1;
else if (x < min_last_element[mid])
right = mid - 1;
else
return mid;
}
return left;
}
static int findLongestIncreasingSubseq(int[] A, int size) {
min_last_element[0] = A[0];
lengthOfLIS = 1;
for (int i = 1; i < size; i++) {
if (A[i] > min_last_element[lengthOfLIS - 1]) {//case 1
min_last_element[lengthOfLIS] = A[i];
lengthOfLIS++;
} else {//case 2
int pos = binarySearch(min_last_element, lengthOfLIS, A[i]);
min_last_element[pos] = A[i];
}
}
return lengthOfLIS;
}
} |
|
