具有子基线长度的递归子基线

Question

我试着做一个递归函数，它计算最大的子回文。你知道吗

例如最大的子Pal。因为“character”是“carac”。你知道吗

到目前为止，我已经实现了我的目标，但是只使用了一个全局变量“length”来添加我的值，但是如果有人能告诉我如何只使用递归调用来实现这一点，那就太好了。我首先尝试给函数第二个参数（length=0），并在调用函数时向其添加值，但无法使其正常工作。你知道吗

这是我的密码：

length = 0

def subpalindrom(s):
    global length
    if len(s) == 1:
        length += 1
        return True, length

    if len(s) == 0:
        return True, length

    elif s[0] != s[-1]:

        for i in range(len(s) - 1, int(len(s) / 2) - 1, -1):  # search right half, if there is smth. equal

        if s[0] == s[i]:
            length += 2
            return subpalindrom(s[1:i])  # if smth. is equal slice it, add length

        elif i == int(len(s) / 2):
            # if index i is at half of the string and nothing was found, continue with next val on left half
            return subpalindrom(s[1:])
    else:
        length += 2
        return subpalindrom(s[1:-1])


print(subpalindrom("character"))

如果有人能告诉我怎么看这个函数的时间复杂度，那就太棒了。我想说是O（对数n），但这只是猜测。你知道吗

编辑：T（n）=T（n-2）+n/2？ T（n-2）表示递归调用（因为我们将2个元素切掉），而+n/2表示for循环？你知道吗

谢谢你的时间！你知道吗

Answer 1

如果有人对此感兴趣，下面是我的处理方法：

def subpalindrom(l, r, w):
    if l == r:
        return 1
    if l > r:
        return 0
    if w[l] == w[r]:
        return 2 + subpalindrom(l + 1, r - 1, w)
    else:
        return max(subpalindrom(l + 1, r, w), subpalindrom(l, r - 1, w))


print(subpalindrom(0, len("character")-1, "character"))