Cohesity
Online AssessmentMaximum Sum Subsequence with Equal First and Last Element
Given an array arr, find the subsequence (minimum length 2) with the maximum sum, such that the first and last elements of the subsequence are equal.
A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array.
Return the maximum possible sum of such a subsequence.
- ▸arr: an array of integers.
- ▸A single integer: the maximum sum of a valid subsequence (length ≥ 2, first element == last element).
- 1 ≤ len(arr) ≤ 10^5
- -10^5 ≤ arr[i] ≤ 10^5
arr = [1000, 100, 1, 2, -1, 1]
4
The only equal pair is the two 1s, at indices 2 and 5.
Take both 1s, keep the positive 2 between them and skip the -1: [1, 2, 1].
The sum is 1 + 2 + 1 = 4.
Between the two equal ends, take every positive element and skip every negative one. Let P[k] be the sum of max(0, arr[t]) for t < k. For a right end j with value v, the best sum is v + P[j] + max over earlier i with arr[i] = v of (v - P[i + 1]). Keep that maximum per value in a hash map while scanning left to right.