# Python-求一道codility算法题的时间复杂度

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:
def 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.

`def getMaxIndex(arr, min, max):    mid = min    maxValue = arr[min]    for index in range(min,max+1):        if arr[index] > maxValue:            mid = index            maxValue = arr[mid]        print str(index) + "****" + str(mid) +"-----" + str(max) + "====" + str(maxValue)    print "----" + str(mid)    return middef maxL(arr, min, max):    if min == max:        return 1    if (max - min) == 1:        return 2    mid = getMaxIndex(arr, min, max)    if mid == max:        return maxL(arr, min, mid-1)+1    if mid == min:        return maxL(arr, mid+1, max)+1    tmpA = maxL(arr, min, mid-1)    tmpB = maxL(arr, mid+1, max)    print "++++" + str(tmpA) + "+++" + str(tmpB)    if tmpA > tmpB:        return tmpA+1    else:        return tmpB+1testArr = [9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4]print maxL(testArr, 0, len(testArr)-1)`

### 评论（1）

2017-03-14 1 楼

B[i] < B[i+1], 对任意i < M
M = K，或者B[M] > B[M+1]

int stack[MAX_N][2]; //满足空间O(n)的条件
int stackptr = 0;

int maxL = 0; //最终结果

for(int i = 0; i < N; i++)
{
int F2, F = 0;
//F 记录F[G[m]]，即堆栈中的数的最大递减序列长度。由向左递减和向右递减中的最大值得到；而向右递减是利用G自身的性质计算。
//F2 记录F2[i]，即i起始最大向左递减序列长度；它由F求得。
while(stackptr > 0 && stack[stackptr-1][0] < A[n])
{
if(F + 1 > stack[stackptr-1][1])
{
F = F + 1;
}
else
{
F = stack[stackptr-1][1];
}
//出栈
stackptr--;
}
//因为F是递增的，所以只要用F的最终值即可。
F2 = F + 1;
if(F2 + stackptr > maxL)
{
maxL = F2 + stackptr;
}
//进栈
stack[stackptr][0] = A[n];
stack[stackptr][1] = F2;
stackptr++;
}

1904 主题
5597 回复
19014 人气