长度为子回文的递归子回文

Question

我正在尝试制作一个递归函数，它计算最大的子回文。

例如，"字符"的最大子像素是"carac"。

到目前为止，我已经实现了我的目标，但只是使用了一个全局变量"长度"来添加我的值，但如果有人能向我展示如何只使用递归调用来实现这一点，那就太好了。我首先尝试给这个函数一个第二个参数(长度=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(logn(，但这只是一个猜测。

编辑：T(n(=T(n-2(+n/2？T(n-2(用于递归调用(因为我们将2个元素切片(，+n/2用于for循环？

感谢您抽出时间！

Answer 1

Sry对后期共享感兴趣，但如果有人感兴趣，以下是我的处理方式：

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"))