Function maxALEminB

DP/MaxASubarrayLessThanMinBSubarray.py:83–161

思路与前一致，前一版的主要瓶颈在于有太多重复的数据，若可以将这些重复的数据统计到一起，可以极大的减少对比次数。 [[3], [2], [1]] 现在变为 [[(3, 1)], [(2, 1)], [(1, 1)]] 即缩小重复的数据的检测结果。 例： [5, 6, 5, 3, 1, 8, 1, 1, 3, 5], [[5], [6, 6], [5, 6, 6], [3, 5, 6, 6], [1, 3, 5, 6, 6], [8, 8, 8, 8, 8, 8],

(a, b)

# 

def maxALEminB(a, b):
    """
        思路与前一致，前一版的主要瓶颈在于有太多重复的数据，若可以将这些重复的数据统计到一起，可以极大的减少对比次数。
        [[3], [2], [1]]
        现在变为 
        [[(3, 1)], [(2, 1)], [(1, 1)]]
        即缩小重复的数据的检测结果。
        例：
        [5, 6, 5, 3, 1, 8, 1, 1, 3, 5],
        [[5], [6, 6], [5, 6, 6], [3, 5, 6, 6], [1, 3, 5, 6, 6], [8, 8, 8, 8, 8, 8], ...]
        dp1的检测为，若当前的值大于之前中的值的某一个[-1:0]，从前到后是按升序排列的。
                    就从最初出现的那个地方截断，之前的值全部替换为此最大值，若没有一个大于的，则直接将之前的追加到当前的结果中。
        dp2的检测只将 大于 变为 小于。

        关于对比：
            每一组的个数可能不同，但总量是一致的。
            两组同时取出自己的一个数据，若b > a则结果中加上 b 和 a 中出现的次数较少的一个。并减去，开始下一轮，b或a中任意一个的出现次数为0时，
            取出相应的本组的下一个数据，同时为0时开始下一轮循环。
    """
    dp1 = [[[i, 1]] for i in a]
    dp2 = [[[i, 1]] for i in b]

    # [
    #  [
    #   [i, 1]
    #  ]
    # ]
    for i in range(1, len(dp1)):
        value = dp1[i][0]
        j = dp1[i-1]

        # 二次优化后提高了 0.2 s.
        if j[0][0] > value[0]:
            dp1[i].extend(j)
            continue

        for x in range(len(j)-1, -1, -1):
            x2 = j[x]
            if x2[0] <= value[0]:
                dp1[i] = [[value[0], sum([t[1] for t in j[:x+1]])+1]] + j[x+1:]
                break

    for i in range(1, len(dp2)):
        value = dp2[i][0]
        j = dp2[i-1]
        if j[0][0] <= value[0]:
            dp2[i].extend(j)
            continue

        for x in range(len(j)-1, -1, -1):
            x2 = j[x]
            if x2[0] >= value[0]:
                dp2[i] = [[value[0], sum([t[1] for t in j[:x+1]])+1]] + j[x+1:]
                break

    result = 0
    for i, j in zip(dp1, dp2):
        valueA = 0