最大子阵列的长度使得第一元素大于最后一个元素

Question

我得到了一个数组.我需要找到第一个元素大于最后一个元素的最大子数组的长度.例如5 4 3 2 1.最大子阵列的长度是5,因为第一个元素5大于最后一个元素1.另一个例子,5 10 4 7 9 8.长度再次为5,数组从10开始并一直到最后一个元素.我知道天真的方法,即O(n²),但需要更好的方法.

Answer 1

您可以尝试应用毛虫方法，该方法的复杂度为 O(n)：

这个想法是使用两个索引，一个用于头部，另一个用于尾部以及最大长度变量。然后，只要条件有效，您就尝试将头部前进：从头部到数组末尾的子序列中的最小值小于尾部的值。

如果由于条件不满足而无法使头部前进，则可以使尾部前进。因此，它类似于毛毛虫，在移动时先推进头部，然后推进尾巴。

That minimum can be pre-calculated in a previous iteration over the array.

This is a possible implementation in python:

def subSeqLen(arr):
    head = 0
    tail = 0
    maxLength = 0
    minFromLast = [arr[-1]]*len(arr)
    for i in xrange(len(arr)-2, -1, -1):
        minFromLast[i] = min(minFromLast[i+1], arr[i])
    while head >= tail and head < len(arr):
        if arr[tail]>arr[head] and head-tail+1 > maxLength:
            maxLength = head-tail+1
        if head < len(arr)-1 and minFromLast[head+1]<=arr[tail]:
            head += 1
        else:
            tail += 1
            head = max(head, tail)
    return maxLength