k**n
发帖数: 3989 | 1 靠，，毕业后就没看过这种东东。。。读题就晕了。。
A non-empty zero-indexed array A containing N different integers is given.
We are looking for the longest possible sequence built from elements of A, A
[B[0]], A[B[1]], ..., A[B[K]], satisfying the following conditions:
The sequence must be decreasing; that is, A[B[0]] > A[B[1]] > ... >
A[B[K]].
For any two consecutive elements of the sequence, A[B[I]] and A[B[I+
1]], all the elements of A between them must be smaller than them; that is,
for any J = MIN(B[I], B[I+1]) + 1, ..., MAX(B[I], B[I+1]) - 1, we have A[J]
< A[B[I+1]].
Write a function:
function sequence(A);
that, given a zero-indexed array A containing N different integers, computes
the maximum length of a sequence satisfying the above conditions.
For example, for the following array A:
A[0] = 9 A[1] = 10 A[2] = 2
A[3] = -1 A[4] = 3 A[5] = -5
A[6] = 0 A[7] = -3 A[8] = 1
A[9] = 12 A[10] = 5 A[11] = 8
A[12] = -2 A[13] = 6 A[14] = 4
the function should return 6.
A sequence of length 6 satisfying the given conditions can be as follows:
A[9] = 12 A[1] = 10 A[4] = 3
A[8] = 1 A[6] = 0 A[7] = -3
Assume that:
the elements of A are all distinct;
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [-1,000,000,
000..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (
not counting the storage required for input arguments).
Elements of input arrays can be modified.
Copyright 2009–2012 by Codility Limited. All Rights Reserved. Unauthorized
copying, publication or disclosure prohibited.
PS：再看一遍，，觉得还是没看懂：For any two consecutive elements of the
sequence, A[B[I]] and A[B[I+1]], all the elements of A between them must be
smaller than them; that is, for any J = MIN(B[I], B[I+1]) + 1, ..., MAX(B[I]
, B[I+1]) - 1, we have A[J] < A[B[I+1]]. | vn
发帖数: 6191 | 2 今天做了2道 做的怎么样不知道 但这些题目挺好玩的~~
个人觉得这个方式考考我这种虾米不错 | i***e
发帖数: 452 | |
|
