Maximum Median Sum of Subsequences of Size 3

Maximum Median Sum of Subsequences of Size 3

What is this problem about?

The Maximum Median Sum of Subsequences of Size 3 coding problem asks you to partition an array into as many non-overlapping triplets as possible (or select triplets) and maximize the total sum of medians across all selected triplets. For each triplet, the median is the middle value when the three elements are sorted. This combines combinatorial selection with optimization of a statistical function.

Why is this asked in interviews?

Amazon uses this problem to test greedy reasoning about median maximization in groups. The key insight: to maximize the median of a triplet, you want the two largest elements of the triplet to "waste" as little as possible. Sorting and pairing greedily — always taking the largest available as the greatest element and the second-largest as the median — maximizes the total median sum.

Algorithmic pattern used

Greedy with sorting: Sort the array in descending order. For each triplet, greedily pick the top available element as the "max", the next as the "median" (this contributes to the answer), and any remaining element as the "min". By sorting descending and taking every other element starting from index 1 (0-indexed), you maximize the sum of medians. The formula: sum all elements at indices 1, 3, 5, ... (every second element starting from the second-largest after sorting).

Example explanation

Array: [3, 5, 2, 7, 4, 1], select as many triplets as possible.

• Sorted descending: [7, 5, 4, 3, 2, 1].
• Triplet 1: [7, 5, 4] → median = 5.
• Triplet 2: [3, 2, 1] → median = 2.
• Sum of medians = 5 + 2 = 7.

In descending sorted order, medians are at indices 1, 3, 5: 5, 3, 2? Wait — triplet 2 is [3,2,1], median=2, which is index 4 in descending order. Pattern: indices 1, 4 for two triplets. The exact indexing depends on triplet size and count. The greedy pairing ensures medians are maximized.

Common mistakes candidates make

• Trying to optimize each triplet independently: A locally optimal triplet choice can ruin future triplets. Global sorting and greedy pairing is necessary.
• Forgetting the "median" is the 2nd element in a sorted triple: The smallest element in each triplet is "wasted" on minimizing loss.
• Incorrect index pattern: The median indices in the sorted array depend on triplet size. For size-3 groups sorted descending, medians fall at positions 1, 4, 7, ...

Interview preparation tip

For the Array Math Sorting Game Theory Greedy interview pattern, whenever a problem involves "median of groups," sort and identify the index pattern for medians. In competitive programming, "maximize sum of medians in size-k groups" always has a clean greedy: sort descending, pick every k-1 elements starting from position 1. Practice deriving this pattern for k=3 and k=5.