解题思路本题的核心是动态规划 单调队列优化。状态定义dp[i][j] 表示从前 i 个元素中选出 j 个合法子数组的最大和。转移方程· 不选第 i 个元素dp[i][j] dp[i-1][j]· 选第 i 个元素作为最后一个子数组的右端点设该子数组左端点为 k需满足 i-r k i-ldp[i][j] max(dp[k][j-1] prefix[i] - prefix[k])优化对于固定的 j候选 k 的窗口 [i-r, i-l] 随 i 滑动用单调递减队列维护 dp[k][j-1] - prefix[k] 的最大值将复杂度从 O(n²·m) 降为 O(n·m)。---C语言完整实现c#include stdio.h#include stdlib.h#include limits.h// ---------- 单调队列存储下标----------typedef struct {int *data;int head, tail;} Deque;void initDeque(Deque *dq, int cap) {dq-data (int*)malloc(cap * sizeof(int));dq-head 0;dq-tail 0;}void freeDeque(Deque *dq) {free(dq-data);}int isEmpty(Deque *dq) {return dq-head dq-tail;}int front(Deque *dq) {return dq-data[dq-head];}int back(Deque *dq) {return dq-data[dq-tail - 1];}void pushBack(Deque *dq, int val) {dq-data[dq-tail] val;}void popFront(Deque *dq) {dq-head;}void popBack(Deque *dq) {dq-tail--;}// ---------- 主函数 ----------long long maximumSum(int* nums, int n, int m, int l, int r) {// 1. 前缀和long long *prefix (long long*)malloc((n 1) * sizeof(long long));prefix[0] 0;for (int i 0; i n; i) {prefix[i 1] prefix[i] nums[i];}const long long NEG -4e18;// 2. dp[j][i]前i个元素中选j个子数组的最大和// 用二维数组方便理解n1000内存足够long long **dp (long long**)malloc((m 1) * sizeof(long long*));for (int j 0; j m; j) {dp[j] (long long*)malloc((n 1) * sizeof(long long));for (int i 0; i n; i) {dp[j][i] NEG;}}// 选0个子数组任何前缀和都为0for (int i 0; i n; i) {dp[0][i] 0;}// 3. 外层子数组个数for (int j 1; j m; j) {Deque dq;initDeque(dq, n 1);// ptr 是即将加入队列的候选左端点// 对于当前 i候选左端点 k 需满足i - r k i - lint ptr 0;for (int i 1; i n; i) {// 3a. 将新候选左端点加入队列// 候选左端点 k i - l 首次进入窗口while (ptr i - l) {// 只有 dp[j-1][ptr] 有效时才加入if (dp[j-1][ptr] ! NEG) {long long val dp[j-1][ptr] - prefix[ptr];// 维护单调递减while (!isEmpty(dq) (dp[j-1][back(dq)] - prefix[back(dq)]) val) {popBack(dq);}pushBack(dq, ptr);}ptr;}// 3b. 移除窗口左侧过期的候选k i - rwhile (!isEmpty(dq) front(dq) i - r) {popFront(dq);}// 3c. 不选 nums[i-1]dp[j][i] dp[j][i-1];// 3d. 选 nums[i-1] 作为最后一个子数组的右端点if (!isEmpty(dq)) {int bestK front(dq);long long candidate prefix[i] dp[j-1][bestK] - prefix[bestK];if (candidate dp[j][i]) {dp[j][i] candidate;}}}freeDeque(dq);}// 4. 答案选 1..m 个子数组的最大值题目要求至少一个、至多m个long long ans NEG;for (int j 1; j m; j) {if (dp[j][n] ans) ans dp[j][n];}// 5. 释放内存for (int j 0; j m; j) {free(dp[j]);}free(dp);free(prefix);return ans;}---关键细节说明要点 说明前缀和 prefix[i] 表示前 i 个元素的和子数组 [k1, i] 的和 prefix[i] - prefix[k]候选左端点范围 子数组长度在 [l, r]右端点为 i 时左端点 k 满足 i-r k i-l单调队列维护 队列中按下标递增存储队头是 dp[j-1][k] - prefix[k] 最大的候选至少一个 最终答案遍历 j1..m 取最大值而非只取 dp[m][n]处理全负数 dp[0][i]0 表示不选任何子数组但最终答案只从 j1 中取确保至少选一个时间复杂度 O(n·m)空间复杂度 O(n·m)n≤1000可接受。
