Maximum strength of k disjoint subarrays

Array Dynamic Programming Prefix Sum

27.5% acceptance

Feb 25, 2026

174

You are given an array of integers nums with length n, and a positive odd integer k. Select exactly k disjoint subarrays sub1, sub2, ..., subk from nums such that the last element of subi appears before the first element of sub{i+1} for all 1 <= i <= k-1. The goal is to maximize their combined strength. The strength of the selected subarrays is defined as: strength = k * sum(sub1)- (k - 1) * sum(sub2) + (k - 2) * sum(sub3) - ... - 2 * sum(sub{k-1}) + sum(subk) Return the maximum possible strength.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_strength(nums: Vec<i32>, k: i32) -> i64 {
    let n = nums.len();
    let k = k as usize;
    const NEG_INF: i64 = i64::MIN / 2;
    // dp_out[j] = max strength with j complete subarrays, currently outside
    // dp_in[j]  = max strength with j subarrays started, currently inside j-th
    let mut dp_out = vec![NEG_INF; k + 1];
    let mut dp_in = vec![NEG_INF; k + 1];
    dp_out[0] = 0;
    for i in 0..n {
      let mut new_out = dp_out.clone();
      let mut new_in = vec![NEG_INF; k + 1];
      for j in 1..=k {
        // mult for j-th subarray: (k-j+1) * (-1)^(j-1)
        let sign = if j % 2 == 1 { 1i64 } else { -1i64 };
        let mult = (k - j + 1) as i64 * sign;
        // Start j-th subarray at position i (from dp_out[j-1])
        if dp_out[j-1] != NEG_INF {
          let v = dp_out[j-1] + mult * nums[i] as i64;
          if v > new_in[j] { new_in[j] = v; }
        }
        // Continue j-th subarray through position i (from dp_in[j])
        if dp_in[j] != NEG_INF {
          let v = dp_in[j] + mult * nums[i] as i64;
          if v > new_in[j] { new_in[j] = v; }
        }
        // End j-th subarray at position i
        if new_in[j] != NEG_INF && new_in[j] > new_out[j] {
          new_out[j] = new_in[j];
        }
      }
      dp_out = new_out;
      dp_in = new_in;
    }
    dp_out[k].max(dp_in[k])
  }
}