有没有一种方法可以计算镜像时相同的最长子字符串或子列表

Question

所以我需要找到可以镜像的最长子列表，知道元素 ex 的数量：

n = 5

my_list = [1,2,3,2,1]

这是我的代码：

n = int(input())

my_list = list(map(int, input().split()))

c = 0

s1 = my_list

x = 0

i = 0

while i < n:

    s2 = s1[i:]

    if s2 == s2[::-1]:

        if c <= len(s2):

            c = len(s2)

    if i >= n-1:

        i = 0

        n = n - 1

        s1 = s1[:-1]

    i += 1

print(c)

正如我们所看到的，镜像时列表是相同的，但是当结果不是预期的n = 10时。my_list = [1,2,3,2,1,332,6597,6416,614,31]35

Answer 1

我的解决方案是将每次迭代中的数组拆分为左数组和右数组，然后反转左数组。接下来，比较每个数组中的每个元素，并在元素相同时将长度变量加一。def longest_subarr(a):&nbsp; &nbsp; longest_exclude = 0&nbsp; &nbsp; for i in range(1, len(a) - 1):&nbsp; &nbsp; &nbsp; &nbsp; # this excludes a[i] as the root&nbsp; &nbsp; &nbsp; &nbsp; left = a[:i][::-1]&nbsp; &nbsp; &nbsp; &nbsp; # this also excludes a[i], needs to consider this in calculation later&nbsp; &nbsp; &nbsp; &nbsp; right = a[i + 1:]&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; max_length = min(len(left), len(right))&nbsp; &nbsp; &nbsp; &nbsp; length = 0&nbsp; &nbsp; &nbsp; &nbsp; while(length < max_length and left[length] == right[length]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; length += 1&nbsp; &nbsp; &nbsp; &nbsp; longest_exclude = max(longest_exclude, length)&nbsp; &nbsp; # times 2 because the current longest is for the half of the array&nbsp; &nbsp; # plus 1 to include to root&nbsp; &nbsp; longest_exclude = longest_exclude * 2 + 1&nbsp; &nbsp; longest_include = 0&nbsp; &nbsp; for i in range(1, len(a)):&nbsp; &nbsp; &nbsp; &nbsp; # this excludes a[i] as the root&nbsp; &nbsp; &nbsp; &nbsp; left = a[:i][::-1]&nbsp; &nbsp; &nbsp; &nbsp; # this includes a[i]&nbsp; &nbsp; &nbsp; &nbsp; right = a[i:]&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; max_length = min(len(left), len(right))&nbsp; &nbsp; &nbsp; &nbsp; length = 0&nbsp; &nbsp; &nbsp; &nbsp; while(length < max_length and left[length] == right[length]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; length += 1&nbsp; &nbsp; &nbsp; &nbsp; longest_include = max(longest_include, length)&nbsp; &nbsp; # times 2 because the current longest is for the half of the array&nbsp; &nbsp; longest_include *= 2&nbsp; &nbsp; return max(longest_exclude, longest_include)&nbsp; &nbsp;&nbsp;print(longest_subarr([1, 4, 3, 5, 3, 4, 1]))print(longest_subarr([1, 4, 3, 5, 5, 3, 4, 1]))print(longest_subarr([1, 3, 2, 2, 1]))这涵盖了奇数长度子数组[a, b, a]和偶数长度子数组的测试用例[a, b, b, a]。

Answer 2

由于您需要可以镜像的最长序列，因此这里有一个简单的 O(n^2) 方法。转到每个索引，以它为中心，如果数字相等，则向左和向右扩展，一次一步。否则中断，并移动到下一个索引。def longest_mirror(my_array):&nbsp;&nbsp; &nbsp; maxLength = 1&nbsp;&nbsp;&nbsp; &nbsp; start = 0&nbsp; &nbsp; length = len(my_array)&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; low = 0&nbsp; &nbsp; high = 0&nbsp;&nbsp;&nbsp; &nbsp; # One by one consider every character as center point of mirrored subarray&nbsp; &nbsp; for i in range(1, length):&nbsp;&nbsp; &nbsp; # checking for even length subarrays&nbsp; &nbsp; &nbsp; &nbsp; low = i - 1&nbsp; &nbsp; &nbsp; &nbsp; high = i&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; while low >= 0 and high < length and my_array[low] == my_array[high]:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if high - low + 1 > maxLength:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = low&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxLength = high - low + 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; low -= 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; high += 1&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # checking for even length subarrays&nbsp; &nbsp; &nbsp; &nbsp; low = i - 1&nbsp; &nbsp; &nbsp; &nbsp; high = i + 1&nbsp; &nbsp; &nbsp; &nbsp; while low >= 0 and high < length and my_array[low] == my_array[high]:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if high - low + 1 > maxLength:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = low&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxLength = high - low + 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; low -= 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; high += 1&nbsp;&nbsp;&nbsp; &nbsp; return maxLength