Maximum and minimum sums of at most size k subsequences

Array Math Dynamic Programming Sorting Combinatorics

21.6% acceptance

Feb 25, 2026

147

You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subsequences of nums with at most k elements. Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_max_sums(mut nums: Vec<i32>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    nums.sort();
    let n = nums.len();
    let k = k as usize;

    fn pow_mod(mut b: i64, mut e: usize, md: i64) -> i64 {
      let mut r = 1i64; b %= md;
      while e > 0 { if e&1==1 { r=r*b%md; } b=b*b%md; e>>=1; } r
    }

    let max_n = n + 1;
    let mut fact = vec![1i64; max_n + 1];
    for i in 1..=max_n { fact[i] = fact[i-1] * i as i64 % MOD; }
    let mut inv_fact = vec![1i64; max_n + 1];
    inv_fact[max_n] = pow_mod(fact[max_n], (MOD-2) as usize, MOD);
    for i in (0..max_n).rev() { inv_fact[i] = inv_fact[i+1] * (i+1) as i64 % MOD; }
    let comb = |a: usize, b: usize| -> i64 {
      if b > a { return 0; }
      fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD
    };

    // sum_max: for each nums[i] as maximum, it contributes nums[i] * sum_{j=0}^{min(k-1,i)} C(i,j)
    // sum_min: for each nums[i] as minimum, it contributes nums[i] * sum_{j=0}^{min(k-1,n-1-i)} C(n-1-i,j)
    let mut ans = 0i64;
    for i in 0..n {
      let mut ways_max = 0i64;
      for j in 0..=(k-1).min(i) { ways_max = (ways_max + comb(i, j)) % MOD; }
      let mut ways_min = 0i64;
      let right = n - 1 - i;
      for j in 0..=(k-1).min(right) { ways_min = (ways_min + comb(right, j)) % MOD; }
      ans = (ans + nums[i] as i64 % MOD * (ways_max + ways_min) % MOD) % MOD;
    }
    ans as i32
  }
}