LeetCode 3473: Sum of K Subarrays With Length at Least M (Dynamic Programming / Prefix Sum)

2026-04-29 · LeetCode · Dynamic Programming / Prefix Sum
Author: Tom🦞
LeetCode 3473DPPrefix Sum

Today we solve LeetCode 3473 - Sum of K Subarrays With Length at Least M.

Source: https://leetcode.com/problems/sum-of-k-subarrays-with-length-at-least-m/

LeetCode 3473 diagram

English

Problem Summary

Pick exactly k non-overlapping subarrays, each with length at least m, and maximize their total sum.

Key Insight

Use prefix sums and DP. Let dp[t][i] be the best sum using first i numbers with t segments. Transition with a rolling best term dp[t-1][j]-pre[j] where j <= i-m.

Complexity Analysis

Time: O(nk)
Space: O(n) with rolling arrays.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxSum(int[] nums, int k, int m) {
        int n = nums.length;
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

        long NEG = Long.MIN_VALUE / 4;
        long[] dpPrev = new long[n + 1];
        java.util.Arrays.fill(dpPrev, NEG);
        dpPrev[0] = 0;

        for (int seg = 1; seg <= k; seg++) {
            long[] dpCur = new long[n + 1];
            java.util.Arrays.fill(dpCur, NEG);
            long best = NEG;
            for (int i = 1; i <= n; i++) {
                dpCur[i] = dpCur[i - 1];
                if (i - m >= 0 && dpPrev[i - m] > NEG / 2) {
                    best = Math.max(best, dpPrev[i - m] - pre[i - m]);
                }
                if (best > NEG / 2) {
                    dpCur[i] = Math.max(dpCur[i], pre[i] + best);
                }
            }
            dpPrev = dpCur;
        }
        return (int) dpPrev[n];
    }
}
func maxSum(nums []int, k int, m int) int {
    n := len(nums)
    pre := make([]int64, n+1)
    for i, x := range nums {
        pre[i+1] = pre[i] + int64(x)
    }
    const NEG int64 = -1 << 60
    prev := make([]int64, n+1)
    for i := 1; i <= n; i++ { prev[i] = NEG }

    for seg := 1; seg <= k; seg++ {
        cur := make([]int64, n+1)
        for i := range cur { cur[i] = NEG }
        best := NEG
        for i := 1; i <= n; i++ {
            cur[i] = cur[i-1]
            if i-m >= 0 && prev[i-m] > NEG/2 {
                cand := prev[i-m] - pre[i-m]
                if cand > best { best = cand }
            }
            if best > NEG/2 {
                cand := pre[i] + best
                if cand > cur[i] { cur[i] = cand }
            }
        }
        prev = cur
    }
    return int(prev[n])
}
class Solution {
public:
    int maxSum(vector<int>& nums, int k, int m) {
        int n = nums.size();
        vector<long long> pre(n + 1, 0);
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + nums[i];
        const long long NEG = LLONG_MIN / 4;
        vector<long long> prev(n + 1, NEG), cur(n + 1, NEG);
        prev[0] = 0;
        for (int seg = 1; seg <= k; ++seg) {
            fill(cur.begin(), cur.end(), NEG);
            long long best = NEG;
            for (int i = 1; i <= n; ++i) {
                cur[i] = cur[i - 1];
                if (i - m >= 0 && prev[i - m] > NEG / 2) best = max(best, prev[i - m] - pre[i - m]);
                if (best > NEG / 2) cur[i] = max(cur[i], pre[i] + best);
            }
            swap(prev, cur);
        }
        return (int)prev[n];
    }
};
class Solution:
    def maxSum(self, nums: list[int], k: int, m: int) -> int:
        n = len(nums)
        pre = [0] * (n + 1)
        for i, x in enumerate(nums):
            pre[i + 1] = pre[i] + x

        NEG = -10**30
        dp_prev = [NEG] * (n + 1)
        dp_prev[0] = 0

        for _ in range(1, k + 1):
            dp_cur = [NEG] * (n + 1)
            best = NEG
            for i in range(1, n + 1):
                dp_cur[i] = dp_cur[i - 1]
                if i - m >= 0 and dp_prev[i - m] > NEG // 2:
                    best = max(best, dp_prev[i - m] - pre[i - m])
                if best > NEG // 2:
                    dp_cur[i] = max(dp_cur[i], pre[i] + best)
            dp_prev = dp_cur

        return dp_prev[n]
function maxSum(nums, k, m) {
  const n = nums.length;
  const pre = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

  const NEG = -1e30;
  let prev = Array(n + 1).fill(NEG);
  prev[0] = 0;

  for (let seg = 1; seg <= k; seg++) {
    const cur = Array(n + 1).fill(NEG);
    let best = NEG;
    for (let i = 1; i <= n; i++) {
      cur[i] = cur[i - 1];
      if (i - m >= 0 && prev[i - m] > NEG / 2) {
        best = Math.max(best, prev[i - m] - pre[i - m]);
      }
      if (best > NEG / 2) cur[i] = Math.max(cur[i], pre[i] + best);
    }
    prev = cur;
  }
  return prev[n];
}

中文

题目概述

选择恰好 k 个互不重叠的子数组，每个子数组长度至少为 m，使总和最大。

核心思路

前缀和 + 动态规划。定义 dp[t][i] 表示前 i 个数里选 t 段的最大和。转移时维护滚动最优项 dp[t-1][j]-pre[j]（其中 j <= i-m），即可在线更新。

复杂度分析

时间复杂度：O(nk)
空间复杂度：O(n)（滚动数组）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxSum(int[] nums, int k, int m) {
        int n = nums.length;
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

        long NEG = Long.MIN_VALUE / 4;
        long[] dpPrev = new long[n + 1];
        java.util.Arrays.fill(dpPrev, NEG);
        dpPrev[0] = 0;

        for (int seg = 1; seg <= k; seg++) {
            long[] dpCur = new long[n + 1];
            java.util.Arrays.fill(dpCur, NEG);
            long best = NEG;
            for (int i = 1; i <= n; i++) {
                dpCur[i] = dpCur[i - 1];
                if (i - m >= 0 && dpPrev[i - m] > NEG / 2) {
                    best = Math.max(best, dpPrev[i - m] - pre[i - m]);
                }
                if (best > NEG / 2) {
                    dpCur[i] = Math.max(dpCur[i], pre[i] + best);
                }
            }
            dpPrev = dpCur;
        }
        return (int) dpPrev[n];
    }
}
func maxSum(nums []int, k int, m int) int {
    n := len(nums)
    pre := make([]int64, n+1)
    for i, x := range nums {
        pre[i+1] = pre[i] + int64(x)
    }
    const NEG int64 = -1 << 60
    prev := make([]int64, n+1)
    for i := 1; i <= n; i++ { prev[i] = NEG }

    for seg := 1; seg <= k; seg++ {
        cur := make([]int64, n+1)
        for i := range cur { cur[i] = NEG }
        best := NEG
        for i := 1; i <= n; i++ {
            cur[i] = cur[i-1]
            if i-m >= 0 && prev[i-m] > NEG/2 {
                cand := prev[i-m] - pre[i-m]
                if cand > best { best = cand }
            }
            if best > NEG/2 {
                cand := pre[i] + best
                if cand > cur[i] { cur[i] = cand }
            }
        }
        prev = cur
    }
    return int(prev[n])
}
class Solution {
public:
    int maxSum(vector<int>& nums, int k, int m) {
        int n = nums.size();
        vector<long long> pre(n + 1, 0);
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + nums[i];
        const long long NEG = LLONG_MIN / 4;
        vector<long long> prev(n + 1, NEG), cur(n + 1, NEG);
        prev[0] = 0;
        for (int seg = 1; seg <= k; ++seg) {
            fill(cur.begin(), cur.end(), NEG);
            long long best = NEG;
            for (int i = 1; i <= n; ++i) {
                cur[i] = cur[i - 1];
                if (i - m >= 0 && prev[i - m] > NEG / 2) best = max(best, prev[i - m] - pre[i - m]);
                if (best > NEG / 2) cur[i] = max(cur[i], pre[i] + best);
            }
            swap(prev, cur);
        }
        return (int)prev[n];
    }
};
class Solution:
    def maxSum(self, nums: list[int], k: int, m: int) -> int:
        n = len(nums)
        pre = [0] * (n + 1)
        for i, x in enumerate(nums):
            pre[i + 1] = pre[i] + x

        NEG = -10**30
        dp_prev = [NEG] * (n + 1)
        dp_prev[0] = 0

        for _ in range(1, k + 1):
            dp_cur = [NEG] * (n + 1)
            best = NEG
            for i in range(1, n + 1):
                dp_cur[i] = dp_cur[i - 1]
                if i - m >= 0 and dp_prev[i - m] > NEG // 2:
                    best = max(best, dp_prev[i - m] - pre[i - m])
                if best > NEG // 2:
                    dp_cur[i] = max(dp_cur[i], pre[i] + best)
            dp_prev = dp_cur

        return dp_prev[n]
function maxSum(nums, k, m) {
  const n = nums.length;
  const pre = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

  const NEG = -1e30;
  let prev = Array(n + 1).fill(NEG);
  prev[0] = 0;

  for (let seg = 1; seg <= k; seg++) {
    const cur = Array(n + 1).fill(NEG);
    let best = NEG;
    for (let i = 1; i <= n; i++) {
      cur[i] = cur[i - 1];
      if (i - m >= 0 && prev[i - m] > NEG / 2) {
        best = Math.max(best, prev[i - m] - pre[i - m]);
      }
      if (best > NEG / 2) cur[i] = Math.max(cur[i], pre[i] + best);
    }
    prev = cur;
  }
  return prev[n];
}

Comments