3985. Palindromic Subarray Sum
Description
You are given an integer array nums.
Return the maximum possible sum of a subarray of nums that is a palindrome.
Example 1:
Input: nums = [10,10]
Output: 20
Explanation:
The whole array [10,10] is a palindrome. Therefore, the maximum sum is 10 + 10 = 20.
Example 2:
Input: nums = [1,2,3,2,1,5,6]
Output: 9
Explanation:
The contiguous subarray [1,2,3,2,1] is a palindrome. Its sum is 1 + 2 + 3 + 2 + 1 = 9 and it is the maximum sum.
Example 3:
Input: nums = [7,1,2,1,7,3,4,3,4]
Output: 18
Explanation:
The contiguous subarray [7,1,2,1,7] is a palindrome. Its sum is 7 + 1 + 2 + 1 + 7 = 18 and it is the maximum sum.
Example 4:
Input: nums = [1,2,3,4,5]
Output: 5
Explanation:
No subarray with length greater than 1 is a palindrome. The largest element in the array is 5. Therefore, the answer is 5.
Example 5:
Input: nums = [1000]
Output: 1000
Explanation:
The subarray with only one element is a palindrome. Therefore, the answer is 1000.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Solutions
Solution 1
Thinking
\(n\le 10^5\), so expanding every palindrome center is \(O(n^2)\) and may be slow. Every palindromic subarray is either a singleton (so the answer is at least \(\max\textit{nums}\)) or an expansion of equal neighbors around a center.
If values do not repeat too often, center expansion may still run; otherwise equality must be hashed or handled by a palindromic automaton. This directory has no implemented solution yet; the walkthrough stops at center expansion versus the singleton maximum.
1 | |
1 | |
1 | |
1 | |