删除子序列问题

给定一个序列,要求从里面删除一个连续的子序列,使得剩下的序列里含有一个最长的连续递增子序列。

这个题目有O(nlogn)的解法,但是比较复杂,我也没有研究清楚,就先说O（n^2）的算法吧:

最容易想到的是枚举算法(i,j),然后检测能够拼接的最长子序列。当然检测这个步骤需要O(n)，我们有两种方式来解决这个问题.

(1)预处理计算出所有的f(i),g(i)，f(i)代表以第i个元素结束的递增序列,g(i)代表以第i个元素开始的递增序列，这就是一个最长子序列问题,直接动态规划O（N）可解。后面就比较简单了:

def start_length(s):
    n = len(s)
    f = [1]*len(s)
    for i in range(n-2,-1,-1):
        if s[i] < s[i+1]:
            f[i] = f[i+1] + 1
    return f
def end_length(s):
    n = len(s)
    G = [1]*n
    for i in range(1,n):
        if s[i-1]<s[i]:
            G[i] = G[i-1]+1
    return G
def find_seq(s):
    m = 0
    n = len(s)
    F,G = start_length(s),end_length(s)
    print(F,G)
    for i in range(1,n):
        for j in range(i,n-1):
            if s[i-1] <s[j+1]:
                m = max(m,G[i-1]+F[j+1])
    print(m)

(2)这个办法没有上一个好,但是还是说一下,利用滑动窗口的思想来做,我们的目的是计算的时候能够迅速得出左右的子序列的长度,所以就需要维护两个递增的子序列,当左边新进来的元素不能保证递增的序列时,我们要将左边的队列清空再入队。右边的队列也始终保持一个单调递增的性质,每次枚举j,就将右边的队列出队一个元素,并且如果队列为空则需要继续寻找一次。

def growth_seq(s,g,i):
    n = len(s)
    i+=1
    while i < n and (len(g)==0 or g[-1]<s[i]):
        g.append(s[i])
        i+=1

def find_seq2(s):
    n = len(s)
    m = 0
    left = deque()
    left.append(s[0])

    for i in range(1,n):
        right = deque()
        while j<n-1:
            if len(right)==0:
                growth_seq(s,right,j)

            if s[i-1]<s[j+1]:
                m = max(m,len(left)+len(right))

            right.popleft()

        while len(left) and left[-1] > s[i]:
            left.pop()
        left.append(s[i])
    print(m)