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

Question

这是一道codility.com的题目，英文题目如下：

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.

我用python写了一个递归去得到这个结果，但是我不太会估计我的算法的时间复杂度（因为有递归调用），所以希望大侠们能够帮我评估下我的代码的时间复杂度，或者能够给出题目要求的O(n)的解法。以下是我的代码：

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 mid

def 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+1

testArr = [9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4]
print maxL(testArr, 0, len(testArr)-1)

Answer 1

其实你的思路是完全正确的。只是你的算法中间，每次找最大值都要把整个数组遍历一遍，而实际上最大值问题是有递归子问题性质的。要考虑怎么在分解
正如你算法的思路那样：对于任意一个B[m]来说，B[m+1]...B[K]要么都小于B[m]，要么都大于B[m]。（性质(1))
方便起见，对任意的i，如果B[i] < B[i+1]，称为数列在i处“向右”；否则称为数列在i处“向左”。
考虑任意一个满足条件的B[K]，一定存在某个m，使得：m = K，或者B[m] > B[m+1]（也就是说，B[k]从第m项开始向左拐了）。记所有这样的m中间最小的为M，那么一定有：
B[i] < B[i+1], 对任意i < M
M = K，或者B[M] > B[M+1]
也就是说，B[K]可以分解成两个阶段：连续向右的阶段；和一次向左以及之后的阶段。

对于所有的n，0 <= n < N，定义满足条件：B[0] = n的题目中描述的B[k]序列的长度（即K+1）最大的序列为“n起始最大子递减序列”，记为F[n]；
进一步，如果B[0] = n，且K=0或者B[1] > n，满足该条件的所有B[k]序列长度的最大值为“n起始最大向右递减序列”，记为F1[n]；相似的，如果K=0或者B[1] < n，满足条件的所有B[k]序列长度最大的序列为“n起始最大向左递减序列”，记为F2[n]。
显然有F[n] = max(F1[n], F2[n])

对所有的n，0 <= n < N，定义满足条件：B[K] = n，且对所有0 <= i < K，有B[i] < B[i+1]（即连续向右）的题目中描述的B[K]序列的长度（即K+1）最大的序列为“n终结最大连续向右递减序列”，记为G[n]。
显然对于任意的n，如果B[K] = n，则B[K-1]是唯一确定的。进一步地不难发现，G[n]是由G[n-1]中大于A[n]的部分，再加上A[n]组成。

因此有所求答案 = max_n{ |G[n]| + |F2[n]| - 1}，其中|G[n]| |F2[n]|表示序列长度
而同时，如果B[I] = n，B[I+1] < n，则B[I+1]可以取的位置只有有限多个，恰好是G[n-1]中，小于A[n]的部分。

综上所述，大致的算法是这样的：

从左到右处理整个数组。用一个堆栈维护当前的G[n]，并对G[n]中每一项存储F[G[i]]的值。
说不明白的话看代码也许更清楚一点：

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++;
}

因为每个数进栈一次、出栈一次，所以总的时间复杂度是O(n)。