Maximum median sum of subsequences of size 3

Array Math Greedy Sorting Game Theory

65.1% acceptance

Feb 25, 2026

You are given an integer array nums with a length divisible by 3. You want to make the array empty in steps. In each step, you can select any three elements from the array, compute their median, and remove the selected elements from the array. The median of an odd-length sequence is defined as the middle element of the sequence when it is sorted in non-decreasing order. Return the maximum possible sum of the medians computed from the selected elements.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_median_sum(nums: Vec<i32>) -> i64 {
    // Sort descending. Greedily pick the 2nd element (median) of each triplet.
    // Best strategy: sort, then pick n/3 elements as medians - specifically,
    // after sorting descending: pair each element at position 1, 3, 5, ... (0-indexed) as medians.
    // Actually: sort ascending. In each triplet we want median as large as possible.
    // Optimal: sort descending, for each group of 3 the median is the 2nd largest.
    // Greedily: pick medians as every other position starting from 1 among the top 2n/3 elements.
    // Sort descending: indices 0,1,2,3,4,5,...
    // We pick index 1, 3, 5, ..., (2*(n/3)-1)
    let mut nums = nums;
    nums.sort_unstable_by(|a, b| b.cmp(a));
    let k = nums.len() / 3;
    (0..k).map(|i| nums[2 * i + 1] as i64).sum()
  }
}