Sum of k subarrays with length at least m

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

    // dp[t][i] = max sum using t non-overlapping subarrays of len>=m, each ending at index <=i (0-indexed)
    // Transition: dp[t][i] = max(dp[t][i-1], max_{j<=i-m+1}(dp[t-1][j-1] + prefix[i+1]-prefix[j]))
    //           = max(dp[t][i-1], prefix[i+1] + max_{j<=i-m+1}(dp[t-1][j-1] - prefix[j]))
    // Use rolling array and running max.

    let neg_inf = i64::MIN / 2;
    let _prev = vec![neg_inf; n]; // dp[0][i] = 0 for all i (0 subarrays, empty sum)
    let _prev_best = vec![0i64; n + 1]; // prev_best[i] = max dp[0][0..=i-1] - prefix[j] for j in 0..=i
    // Actually: dp[0][i] = 0 for all i. For t=1:
    // dp[1][i] = max_{j=0..=i-m+1}(prefix[i+1] - prefix[j]) = prefix[i+1] - min_{j=0..=i-m+1}(prefix[j])
    // For general t: dp[t][i] = max(dp[t][i-1], prefix[i+1] + max_{j=1..=i-m+2}(dp[t-1][j-1] - prefix[j]))

    // Initialize dp_prev = dp[0][i] = 0 for all i
    let mut dp_prev = vec![0i64; n + 1]; // dp_prev[i] = dp[t-1][i] (i = -1..n-1 mapped to 0..n)
    // dp_prev[0] = dp[t-1][-1] = 0 (empty)

    let mut ans = neg_inf;
    for _t in 1..=k {
      let mut dp_cur = vec![neg_inf; n + 1]; // dp_cur[i+1] = dp[t][i]
      let mut run_max = neg_inf; // max of dp_prev[j] - prefix[j] for j = 0..=i-m+1
      for i in 0..n {
        // Can add j = i+1-m to the running max (subarray of exactly m starts at j, ends at i)
        // j = i - m + 1 (0-indexed start), must be >= 0
        if i + 1 >= m {
          let j = i + 1 - m; // start of subarray ending at i
          // dp_prev[j] = dp[t-1][j-1] where j-1 index means we use dp_prev[j] directly
          let val = dp_prev[j]; // dp[t-1][j-1]
          if val != neg_inf {
            let candidate = val - prefix[j];
            if candidate > run_max { run_max = candidate; }
          }
        }
        // dp_cur[i+1] = max(dp_cur[i], prefix[i+1] + run_max)
        dp_cur[i+1] = dp_cur[i];
        if run_max != neg_inf {
          let v = prefix[i+1] + run_max;
          if v > dp_cur[i+1] { dp_cur[i+1] = v; }
        }
      }
      ans = dp_cur[n];
      dp_prev = dp_cur;
    }
    ans
  }
}