Choose subsequences of length 3 to maximize the sum of their medians.
Problem
You are given an array of integers. Your task is to select elements and form disjoint subsequences of length 3. For each chosen subsequence, take its median value, and add all of these medians together.
Return the maximum possible sum of medians you can obtain.
A subsequence keeps the original relative order of the chosen elements, but because only the median of each group of 3 matters, the key challenge is deciding which values should be grouped together to maximize the total.
Intuition
To maximize the total, you want the median of each group of three to be as large as possible. This usually means pairing a large value with one even larger value and one smaller value that does not reduce the median.
Input Format
- An integer array
nums. - The array length is assumed to allow forming one or more groups of 3 for the intended test cases.
Output Format
- Return a single integer: the maximum possible sum of medians across all selected subsequences of size 3.
Constraints
- Values may be positive, zero, or negative.
- The exact platform constraints are not provided here; solve in near-linear or
O(n log n)time.
Example 1
Input
nums = [2, 1, 3, 4, 5, 6]
Output
9
Explanation
One optimal choice is subsequences [1, 2, 3] and [4, 5, 6]. Their medians are 2 and 5, so the total is 7. A better grouping is [1, 3, 4] and [2, 5, 6], whose medians are 3 and 5, giving 8. If we interpret the task as maximizing medians of size-3 groups over all feasible selections, the highest values are contributed by the middle elements of well-placed triples.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.