Minimum partition score

Array Divide and Conquer Dynamic Programming Queue Prefix Sum Monotonic Queue

33.9% acceptance

Mar 16, 2026

Partition nums into exactly k subarrays, minimize sum of values. Value of subarray = sumArr * (sumArr + 1) / 2.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_partition_score(nums: Vec<i32>, k: i32) -> i64 {
    let n = nums.len();
    let k = k as usize;
    let prefix: Vec<i64> = {
      let mut p = vec![0i64; n + 1];
      for i in 0..n { p[i + 1] = p[i] + nums[i] as i64; }
      p
    };

    #[inline]
    fn cost(prefix: &[i64], m: usize, i: usize) -> i64 {
      let s = prefix[i] - prefix[m];
      s * (s + 1) / 2
    }

    // Divide-and-conquer optimization for DP with quadrangle inequality
    // val(s) = s*(s+1)/2 is convex, so optimal split point is monotone
    fn solve(
      dp: &mut [i64], prev: &[i64], prefix: &[i64],
      lo: usize, hi: usize, opt_lo: usize, opt_hi: usize,
    ) {
      if lo > hi { return; }
      let mid = lo + (hi - lo) / 2;
      let mut best_cost = i64::MAX;
      let mut best_m = opt_lo;
      let bound = opt_hi.min(mid.saturating_sub(1));
      for m in opt_lo..=bound {
        if prev[m] == i64::MAX { continue; }
        let c = prev[m] + cost(prefix, m, mid);
        if c < best_cost {
          best_cost = c;
          best_m = m;
        }
      }
      dp[mid] = best_cost;
      if mid > lo {
        solve(dp, prev, prefix, lo, mid - 1, opt_lo, best_m);
      }
      if mid < hi {
        solve(dp, prev, prefix, mid + 1, hi, best_m, opt_hi);
      }
    }

    // dp[i] = min score partitioning nums[0..i] into j parts
    let mut dp = vec![i64::MAX; n + 1];
    dp[0] = 0;
    // j=1: single partition
    for i in 1..=n {
      dp[i] = cost(&prefix, 0, i);
    }

    for j in 2..=k {
      let prev = dp.clone();
      dp = vec![i64::MAX; n + 1];
      solve(&mut dp, &prev, &prefix, j, n, j - 1, n - 1);
    }
    dp[n]
  }
}