Skip to content

3627. Maximum Median Sum of Subsequences of Size 3

Description

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.

 

Example 1:

Input: nums = [2,1,3,2,1,3]

Output: 5

Explanation:

  • In the first step, select elements at indices 2, 4, and 5, which have a median 3. After removing these elements, nums becomes [2, 1, 2].
  • In the second step, select elements at indices 0, 1, and 2, which have a median 2. After removing these elements, nums becomes empty.

Hence, the sum of the medians is 3 + 2 = 5.

Example 2:

Input: nums = [1,1,10,10,10,10]

Output: 20

Explanation:

  • In the first step, select elements at indices 0, 2, and 3, which have a median 10. After removing these elements, nums becomes [1, 10, 10].
  • In the second step, select elements at indices 0, 1, and 2, which have a median 10. After removing these elements, nums becomes empty.

Hence, the sum of the medians is 10 + 10 = 20.

 

Constraints:

  • 1 <= nums.length <= 5 * 105
  • nums.length % 3 == 0
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Greedy + Sorting

To maximize the sum of medians, we need to select larger elements as medians whenever possible. Since each operation can only select three elements, we can sort the array and then start from index \(n / 3\), selecting every other element (skipping one) until the end of the array. This ensures that we select the largest possible medians.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
class Solution:
    def maximumMedianSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[len(nums) // 3 :: 2])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public long maximumMedianSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long ans = 0;
        for (int i = n / 3; i < n; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    long long maximumMedianSum(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        long long ans = 0;
        for (int i = n / 3; i < n; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func maximumMedianSum(nums []int) (ans int64) {
    sort.Ints(nums)
    n := len(nums)
    for i := n / 3; i < n; i += 2 {
        ans += int64(nums[i])
    }
    return
}

1
2
3
4
5
6
7
8
9
function maximumMedianSum(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = n / 3; i < n; i += 2) {
        ans += nums[i];
    }
    return ans;
}

Comments