d90有啥deal么?# PhotoGear - 摄影器材
S*C
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.
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.