企业官网建设流程全解析

解题思路

本题的核心是动态规划 + 单调队列优化。

状态定义：dp[i][j] 表示从前 i 个元素中选出 j 个合法子数组的最大和。

转移方程：

· 不选第 i 个元素：dp[i][j] = dp[i-1][j]
· 选第 i 个元素作为最后一个子数组的右端点，设该子数组左端点为 k（需满足 i-r <= k <= i-l）：dp[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个子数组的最大和
// 用二维数组，方便理解；n<=1000，内存足够
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个子数组，任何前缀和都为0
for (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 - l
int 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 - r）
while (!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 个元素的和，子数组 [k+1, i] 的和 = prefix[i] - prefix[k]
候选左端点范围 子数组长度在 [l, r]，右端点为 i 时，左端点 k 满足 i-r <= k <= i-l
单调队列维护 队列中按下标递增存储，队头是 dp[j-1][k] - prefix[k] 最大的候选
"至少一个" 最终答案遍历 j=1..m 取最大值，而非只取 dp[m][n]
处理全负数 dp[0][i]=0 表示不选任何子数组，但最终答案只从 j>=1 中取，确保至少选一个

时间复杂度 O(n·m)，空间复杂度 O(n·m)（n≤1000，可接受）。