当前位置：首页 > news >正文

解决leetcode第3985题回文数组求和

news 2026/7/9 6:45:25

3985.回文子数组求和

难度：困难

问题描述：

给你一个整数数组nums。

你的任务是找出nums中一个回文子数组的最大元素和。返回这样的子数组的最大元素和。

子数组是数组中一个连续的非空元素序列。

如果一个子数组正着读和反着读都相同，则称其为回文。

示例1：

输入：nums=[10,10]

输出：20

解释：

整个数组[10,10]是回文子数组。因此，最大元素和为10+10=20。

示例2：

输入：nums=[1,2,3,2,1,5,6]

输出：9

解释：

连续子数组[1,2,3,2,1]是回文子数组。它的元素和为1+2+3+2+1=9，并且这是最大元素和。

示例3：

输入：nums=[7,1,2,1,7,3,4,3,4]

输出：18

解释：

连续子数组[7,1,2,1,7]是回文子数组。它的元素和为7+1+2+1+7=18，并且这是最大元素和。

示例4：

输入：nums=[1,2,3,4,5]

输出：5

解释：

不存在长度大于1的回文子数组。数组中的最大元素是5，因此答案为5。

示例5：

输入：nums=[1000]

输出：1000

解释：

只包含一个元素的子数组也是回文子数组。因此，答案为1000。

提示：

1<=nums.length<=10**5

1<=nums[i]<=10**9

问题分析：

本题思路简单，首先是如何判断回文子数组，这通过函数check_if_it_is_a_palindrome_array(nums)实现，基功能是对于给定的数组nums，判断其是否为回文数组，如果是，返回True，否则返回False，其次通过一个二重循环列举出所有可能的子数组，判断其回文性，把所有的回文子数组及其和以列表的形式找出，最后输出最大和以及对应的子数组即可。

程序如下：

#检查一个数组nums是否为一个回文数组，是返回True，否返回False def check_if_it_is_a_palindrome_array(nums): return nums==nums[::-1] #主程序 nums=eval(input("enter the array nums=")) t=[] n=len(nums) for i in range(n): for j in range(i+1,n+1): s=nums[i:j] if check_if_it_is_a_palindrome_array(s): t.append([s,sum(s)]) t.sort(key=lambda x: x[1]) print(f'连续子数组{t[-1][0]}是回文子数组，它的元素和为{t[-1][1]}')