递归分治最长运行时间

Question

我想实现一个算法，使用分治递归查找数组中整数的最长运行时间

我做了一个有意义的顺序算法，我想我可以用递归来实现。然而，我对如何使用“分而治之”感到困惑，因为我相信这会打破这一局面

例如：

[1,2,3,4,4,4,3,3]

如果将列表一分为二，前4个将与其余4个分离

我已经创建了基本案例，但不确定从那里开始

基本情况：

if(len(myarray) == 0):
    return 0

Answer 1

您可以从中间位置检测到一条数字条纹，将其在每一侧展开，并在该条纹的左侧和右侧的剩余值上递归

返回3条中最长的（左最长、中间条纹、右最长）

def maxrun(A,lo=None,hi=None):
    if lo is None: lo,hi = 0,len(A)-1  # start with the full range
    if lo > hi:  return 0              # empty sub range counts for zero
    if lo == hi: return 1              # single element subrange is one
    mid   = (lo+hi)//2                 # use value in middle of range
    left  = right = mid                # repeated range 
    while left>lo  and A[left-1]  == A[mid]: left  -= 1 # expand left
    while right<hi and A[right+1] == A[mid]: right += 1 # expand right
    return max(right-left+1,maxrun(A,lo,left-1),maxrun(A,right+1,hi)) # recurse


print(maxrun([1,2,3,4,4,4,3,3])) # 3

请注意，当剩余范围大于当前最佳条纹时，只需向下递归即可进一步优化