Medium

题目描述

给你一个整数数组 nums 和两个整数 k 和 m。

返回 k 个不重叠子数组的最大和，其中每个子数组的长度至少为 m。

示例 1：

输入：nums = [1,2,-1,3,3,4], k = 2, m = 2
输出：13
解释：
最优选择是：
- 子数组 nums[3..5]，和为 3 + 3 + 4 = 10（长度为 3 >= m）
- 子数组 nums[0..1]，和为 1 + 2 = 3（长度为 2 >= m）
总和为 10 + 3 = 13。

示例 2：

输入：nums = [-10,3,-1,-2], k = 4, m = 1
输出：-10
解释：
最优选择是将每个元素作为一个子数组。输出为 (-10) + 3 + (-1) + (-2) = -10。

约束条件：

  • 1 <= nums.length <= 2000
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= floor(nums.length / m)
  • 1 <= m <= 3

解题思路

这道题需要找到 k 个不重叠的子数组，每个子数组长度至少为 m，使得总和最大。

思路分析：

  1. 动态规划设计：定义 dp[i][j] 表示在前 j 个元素中选择 i 个子数组的最大和。

  2. 状态转移：对于每个位置 j，我们有两种选择：

    • 不选择以位置 j 结尾的子数组：dp[i][j] = dp[i][j-1]
    • 选择以位置 j 结尾的子数组：枚举所有长度至少为 m 的子数组

  3. 子数组和计算：使用前缀和优化子数组和的计算，避免重复计算。

  4. 边界条件：

    • 当 i = 0 时，不选择任何子数组，和为 0
    • 当 j < m 时，无法形成长度至少为 m 的子数组

算法步骤：

  1. 计算前缀和数组
  2. 初始化 dp 数组
  3. 对每个位置和子数组个数进行状态转移
  4. 返回 dp[k][n]

这种方法时间复杂度为 O(n²k)，空间复杂度为 O(nk)，对于给定的约束条件是高效的。

代码实现

class Solution {
public:
    int maxSum(vector<int>& nums, int k, int m) {
        int n = nums.size();
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, LLONG_MIN));
        
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }
        
        for (int i = 1; i <= k; i++) {
            for (int j = i * m; j <= n; j++) {
                dp[i][j] = dp[i][j - 1];
                
                for (int len = m; len <= j - (i - 1) * m; len++) {
                    int start = j - len;
                    long long subarraySum = prefix[j] - prefix[start];
                    if (dp[i - 1][start] != LLONG_MIN) {
                        dp[i][j] = max(dp[i][j], dp[i - 1][start] + subarraySum);
                    }
                }
            }
        }
        
        return (int)dp[k][n];
    }
};

class Solution:
    def maxSum(self, nums: List[int], k: int, m: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        dp = [[-float('inf')] * (n + 1) for _ in range(k + 1)]
        
        for j in range(n + 1):
            dp[0][j] = 0
        
        for i in range(1, k + 1):
            for j in range(i * m, n + 1):
                dp[i][j] = dp[i][j - 1]
                
                for length in range(m, j - (i - 1) * m + 1):
                    start = j - length
                    subarray_sum = prefix[j] - prefix[start]
                    if dp[i - 1][start] != -float('inf'):
                        dp[i][j] = max(dp[i][j], dp[i - 1][start] + subarray_sum)
        
        return dp[k][n]

public class Solution {
    public int MaxSum(int[] nums, int k, int m) {
        int n = nums.Length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        long[,] dp = new long[k + 1, n + 1];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i, j] = long.MinValue;
            }
        }
        
        for (int j = 0; j <= n; j++) {
            dp[0, j] = 0;
        }
        
        for (int i = 1; i <= k; i++) {
            for (int j = i * m; j <= n; j++) {
                dp[i, j] = dp[i, j - 1];
                
                for (int len = m; len <= j - (i - 1) * m; len++) {
                    int start = j - len;
                    long subarraySum = prefix[j] - prefix[start];
                    if (dp[i - 1, start] != long.MinValue) {
                        dp[i, j] = Math.Max(dp[i, j], dp[i - 1, start] + subarraySum);
                    }
                }
            }
        }
        
        return (int)dp[k, n];
    }
}

var maxSum = function(nums, k, m) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    const dp = Array(k + 1).fill().map(() => Array(n + 1).fill(-Infinity));
    
    for (let j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }
    
    for (let i = 1; i <= k; i++) {
        for (let j = i * m; j <= n; j++) {
            dp[i][j] = dp[i][j - 1];
            
            for (let len = m; len <= j - (i - 1) * m; len++) {
                const start = j - len;
                const subarraySum = prefix[j] - prefix[start];
                if (dp[i - 1][start] !== -Infinity) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][start] + subarraySum);
                }
            }
        }
    }
    
    return dp[k][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²k)，其中 n 为数组长度。需要遍历所有状态 (i,j)，对每个状态枚举所有可能的子数组长度
空间复杂度O(nk)，用于存储 dp 数组和前缀和数组