技术问询：寻找使(均值-中位数)最大化的整数子集

Alright, let's break down how to find the subset that maximizes the value of (mean - median) for a given set of integers. I'll walk through the core logic first, then apply it to your examples to make it concrete.

First, let's get to the core of what we're trying to achieve: we want the mean of the subset to be as large as possible while keeping the median as small as possible. The key insight here is that the optimal subset will almost always have an odd length (I'll explain why briefly later), so we can focus on constructing odd-length subsets to simplify things.

Step-by-Step Approach #

• Sort the original array: This is non-negotiable for working with medians—we need a clear order to pick our median candidate and surrounding elements.
• Iterate over possible median positions: For each element in the sorted array, treat it as the median of a potential subset.
• Construct candidate subsets for each median: For a median candidate at position i (just be consistent with 0/1-indexing), build subsets by:
  • Including the median itself.
  • Adding t elements from the left of the median (the closest t elements to the median, not the smallest ones—this minimizes the negative drag on the mean).
  • Adding t elements from the right of the median (the largest t elements, to maximize the positive lift on the mean).
  • t can range from 0 up to the maximum possible (so we don't run out of elements on either side: t ≤ min(number of elements left of median, number of elements right of median)).
• Calculate (mean - median) for each candidate: Track the candidate with the highest value of this metric—that's your answer.

Why Odd-Length Subsets? #

For even-length subsets, the median is the average of the two middle elements. This tends to raise the median value without a corresponding enough boost to the mean. Odd-length subsets let us fix a single lower median while packing in larger elements to inflate the mean, which almost always gives a better (mean - median) result.

Example Walkthroughs #

Example 1: Input {1,2,3,4} #

First, sort the array: [1,2,3,4]

Let's evaluate each potential median:

• Median = 1: We can only form subsets of length 1 ({1}) or even-length pairs (but those give a median of ~2.5, which makes mean - median 0 or negative). No good.
• Median = 2: We can try t=1 (since we have 1 element left of 2 and 2 elements right of 2):
  • Left element: 1 (only option)
  • Right element: 4 (the largest available)
  • Subset: {1,2,4}
  • Mean = (1+2+4)/3 = 7/3 ≈ 2.333, Median = 2
  • (Mean - Median) = 1/3 ≈ 0.333 (the highest we can get here)
• Median =3: Any subset here will have a median of 3, and the mean will be lower than 3 (e.g., {2,3,4} has mean 3, difference 0; {1,3,4} has mean ~2.666, difference negative).
• Median=4: Only subset is {4}, difference 0.

So the optimal subset is {1,2,4}.

Example 2: Input {1,2,2,3,3} #

Sort the array: [1,2,2,3,3]

Evaluate potential medians:

• Median=2 (second element): Trying t=1 gives subset {1,2,3}, mean=2, median=2, difference 0.
• Median=2 (third element):
  • Try t=1:
    • Left element: 2 (closest to the median on the left)
    • Right element: 3 (largest on the right)
    • Subset: {2,2,3}
    • Mean=(2+2+3)/3=7/3≈2.333, Median=2
    • (Mean-Median)=1/3≈0.333 (the highest here)
  • Try t=2: Subset is the full array, mean=2.2, median=2, difference 0.2 (worse than t=1)
• Median=3: Any subset here will have a median ≥3, and mean will be ≤3, leading to non-positive differences.

Thus the optimal subset is {2,2,3}.

内容的提问来源于stack exchange，提问作者Gaurav Kishore