Maximize cyclic partition score

Array Dynamic Programming

12.5% acceptance

Feb 25, 2026

You are given a cyclic array nums and an integer k. Partition nums into at most k subarrays. As nums is cyclic, these subarrays may wrap around from the end of the array back to the beginning. The range of a subarray is the difference between its maximum and minimum values. The score of a partition is the sum of subarray ranges. Return the maximum possible score among all cyclic partitions.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_score(nums: Vec<i32>, k: i32) -> i64 {
    let n = nums.len();
    if n <= 1 { return 0; }

    // Each useful subarray needs ≥ 2 elements; single-element parts have range 0
    // and can always be merged into a neighbor without decreasing the score.
    // So optimal k ≤ floor(n / 2).
    let k = (k as usize).min(n / 2);
    if k == 0 { return 0; }

    // ── Key insight (灵茶山艾府) ──────────────────────────────────────────
    // There always exists an optimal cyclic partition in which the global
    // maximum is either the FIRST or the LAST element of its subarray.
    // Therefore, we only need to try exactly 2 "break points" instead of n,
    // reducing the outer loop from O(n) to O(1).
    //
    // After breaking the circle we get a linear array.  The range of each
    // linear subarray equals the profit of one stock transaction (long: buy
    // min then sell max; short: sell max then cover min).  Maximising the
    // sum of ranges over ≤ k subarrays is therefore identical to maximising
    // the profit of ≤ k non-overlapping long/short stock transactions —
    // exactly "Best Time to Buy and Sell Stock V" (LC 3573), solvable in
    // O(n·k) with a rolling DP.
    //
    // Total complexity: O(n·k)  (vs. the previous O(n²·k)).
    // ─────────────────────────────────────────────────────────────────────

    // Find index of the global maximum (first occurrence).
    let max_i = nums
      .iter()
      .enumerate()
      .max_by_key(|&(_, v)| v)
      .unwrap()
      .0;

    // Rotation 1: global max at position 0 (leftmost of its subarray).
    let rot1: Vec<i32> = nums[max_i..]
      .iter()
      .chain(nums[..max_i].iter())
      .copied()
      .collect();

    // Rotation 2: global max at position n-1 (rightmost of its subarray).
    let rot2: Vec<i32> = nums[max_i + 1..]
      .iter()
      .chain(nums[..max_i + 1].iter())
      .copied()
      .collect();

    Self::stock_v(&rot1, k).max(Self::stock_v(&rot2, k)).max(0)
  }

  /// Maximum profit of at most `k` non-overlapping long/short transactions
  /// on `prices` — "Best Time to Buy and Sell Stock V" DP.
  ///
  /// States per level j (1 ..= k+1):
  ///   f[j][0]  no open position  (initialised 0 = "fresh budget")
  ///   f[j][1]  long  position open (bought at some earlier price)
  ///   f[j][2]  short position open (sold  at some earlier price)
  ///
  /// Transitions (process j from high → low to avoid reusing within one step):
  ///   f[j][0] ← max(f[j][0], f[j][1] + p, f[j][2] − p)   // close position
  ///   f[j][1] ← max(f[j][1], f[j−1][0] − p)              // open long
  ///   f[j][2] ← max(f[j][2], f[j−1][0] + p)              // open short
  ///
  /// Answer: f[k+1][0]
  fn stock_v(prices: &[i32], k: usize) -> i64 {
    const NEG_INF: i64 = i64::MIN / 2;
    // f[j] = [free, long_open, short_open]
    let mut f = vec![[NEG_INF; 3]; k + 2];
    for j in 1..=k + 1 {
      f[j][0] = 0;
    }
    for &price in prices {
      let p = price as i64;
      for j in (1..=k + 1).rev() {
        f[j][0] = f[j][0].max(f[j][1] + p).max(f[j][2] - p);
        f[j][1] = f[j][1].max(f[j - 1][0] - p);
        f[j][2] = f[j][2].max(f[j - 1][0] + p);
      }
    }
    f[k + 1][0]
  }
}