Given a list of integers, find the maximum sum of a contiguous subarray such that the first and last elements of the subarray are equal.
A subarray must be non-empty and contiguous.
A subarray of length 1 is also valid, because its first and last elements are the same element.
Method Signature
long maximumSumSubarray(List<Integer> nums)
Return the maximum possible sum of a contiguous subarray whose first and last elements are equal.
Constraints
1 ≤ nums.size() ≤ 2 * 10^5-10^9 ≤ nums[i] ≤ 10^9
Examples
Example 1
Method Call: maximumSumSubarray(nums = List.of(1, 2, 3, 2, 1))
Output: 9
Explanation: The entire subarray [1, 2, 3, 2, 1] is valid because the first and last elements are both 1. Its sum is 9, which is the maximum possible.
Example 2
Method Call: maximumSumSubarray(nums = List.of(5, -10, 5, 4, -1, 4))
Output: 7
Explanation: One valid choice is [4, -1, 4], whose first and last elements are both 4. Its sum is 7. The subarray [5, -10, 5] is also valid, but its sum is only 0.
Example 3
Method Call: maximumSumSubarray(nums = List.of(-3, -2, -3))
Output: -2
Explanation: The full subarray [-3, -2, -3] is valid, but its sum is -8. Since a single element subarray is allowed, choosing [-2] gives the maximum valid sum, which is -2.
Example 4
Method Call: maximumSumSubarray(nums = List.of(7, 1, 2, 3))
Output: 7
Explanation: There is no longer valid subarray with equal first and last elements. So the best choice is the single element subarray [7].