我正在尝试创建一个递归函数，它计算最大的子回文。
例如最大的sub.Pal。 “角色”是“carac”。
到目前为止，我已经实现了我的目标，但仅使用全局变量“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(log n) 但这只是一个猜测。
编辑:T(n) = T(n-2) + n/2 ？ T(n-2) 用于递归调用(因为我们切掉了 2 个元素)，而 + n/2 由于 for 循环？
感谢您的宝贵时间!
最佳答案
抱歉分享晚了，但如果有人感兴趣，我是这样处理的:
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"))
关于python - 具有子回文长度的递归子回文，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53655352/