通过将两个相邻的x转换为一个(x + 1)可实现的最大数量

Question

给定一系列N整数,其中1 <= N <= 500数字介于两者之间1 and 50.在一个步骤中,任何两个相邻的相等数字x x可以用一个替换x + 1.这些步骤可达到的最大数量是多少.

例如,如果给定2 3 1 1 2 2则最大可能是4:

2 3 1 1 2 2 ---> 2 3 2 2 2 ---> 2 3 3 2 ---> 2 4 2.

很明显,我应该尝试做得比序列中可用的最大数量更好.但我无法弄清楚一个好的算法.

Answer 1

这是一个暴力解决方案：

function findMax(array A, int currentMax)
    for each pair (i, i+1) of indices for which A[i]==A[i+1] do
        currentMax = max(A[i]+1, currentMax)
        replace A[i],A[i+1] by a single number A[i]+1
        currentMax = max(currentMax, findMax(A, currentMax))
    end for
    return currentMax

Given the array A, let currentMax=max(A[0], ..., A[n])
print findMax(A, currentMax)

该算法终止是因为在每次递归调用中数组都会缩小1。

很明显它是正确的：我们尝试了所有可能的替换序列。

当数组很大并且有很多关于替换的选项时，代码非常慢，但实际上在具有少量可替换对的数组上运行得相当快。（我将尝试根据可替换对的数量来量化运行时间。）

Python 中的简单工作代码：

def findMax(L, currMax):
    for i in range(len(L)-1):
        if L[i] == L[i+1]:
            L[i] += 1
            del L[i+1]
            currMax = max(currMax, L[i])
            currMax = max(currMax, findMax(L, currMax))
            L[i] -= 1
            L.insert(i+1, L[i])
    return currMax

# entry point
if __name__ == '__main__':
    L1 = [2, 3, 1, 1, 2, 2]
    L2 = [2, 3, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2]
    print findMax(L1, max(L1))
    print findMax(L2, max(L2))

第一次调用的结果是4，正如预期的那样。

第二次调用的结果5符合预期；给出结果的序列： 2,3,1,1,2,2,2,2,2,2,2,2, -> 2,3,1,1,3,2,2,2,2 ,2,2 -> 2,3,1,1,3,3,2,2,2,2, -> 2,3,1,1,3,3,3,2,2 -> 2,3 ,1,1,3,3,3,3 -> 2,3,1,1,4,3, -> 2,3,1,1,4,4 -> 2,3,1,1,5