零、前置知识

• 动态规划：理解状态划分与状态转移的基本思想。
• 状态机 DP ：通过构建有限状态自动机，将复杂的过程拆分为若干个状态及其之间的转移关系。
• 最大子数组和：熟悉经典的 Kadane 算法，即如何在 $O(n)$ 时间内求出普通数组的最大连续子数组和。

一、题目大意

给定一个长度为 $n$ 的数组 $a$ 和一个魔法系数 $k$。 你可以选择至多一个连续子数组，将其中的所有元素都乘以 $k$（也可以不进行任何乘法操作，即选择空区间）。 在进行该操作后，求出修改后的数组中非空连续子数组的最大和。

二、思路分析

本题是在经典“最大连续子数组和”的基础上，增加了一次可选的区间乘法操作。我们需要在寻找最大子数组的同时，决定在何处开始乘 $k$，在何处结束乘 $k$。

这是一个经典的状态机动态规划问题。我们可以将决策过程抽象为一个含有 3 个状态的有向无环图（DAG）：

[状态 0: 未开始魔法] ──(乘以 k)──> [状态 1: 正在魔法中] ──(乘以 1)──> [状态 2: 魔法已结束]
       │                                  │                                  │
   (继续保持)                          (继续保持)                          (继续保持)
       └───────> [状态 0]                  └───────> [状态 1]                  └───────> [状态 2]

状态定义

令 dp[i][j] 表示以第 $i$ 个元素结尾的非空连续子数组的最大和，其中第二维 $j$ 表示当前元素所处的状态： * 状态 0 (dp[i][0])：当前元素处于未开始施加魔法的阶段。 * 状态 1 (dp[i][1])：当前元素处于正在施加魔法的阶段（当前元素需要乘以 $k$）。 * 状态 2 (dp[i][2])：当前元素处于魔法已经结束的阶段（此前已有部分元素乘以 $k$，当前元素恢复原值）。

状态转移方程

对于每个元素 $a_i$（以下用 $x$ 代替 $a_i$）：

1. 状态 0 的转移： 当前元素不乘 $k$，且前面也未乘 $k$。它可以是由前一个位置的状态 0 延续而来，或者以当前元素作为新子数组的起点。 $$\text{dp}[i][0] = \max(\text{dp}[i-1][0], 0) + x$$

2. 状态 1 的转移： 当前元素必须乘以 $k$。它可以由以下三种情况转移而来：

   • 状态 0 $\to$ 状态 1：在当前位置开始施加魔法：$\text{dp}[i-1][0] + x \times k$
   • 状态 1 $\to$ 状态 1：延续之前的魔法状态：$\text{dp}[i-1][1] + x \times k$
   • 新起点 $\to$ 状态 1：以当前元素作为新子数组的起点，且直接开始施加魔法：$0 + x \times k$ $$\text{dp}[i][1] = \max(\text{dp}[i-1][0], \text{dp}[i-1][1], 0) + x \times k$$

3. 状态 2 的转移： 当前元素不乘 $k$，但此前已经进行过魔法操作。它可以由以下三种情况转移而来：

   • 状态 1 $\to$ 状态 2：魔法在上一位置结束，当前位置恢复正常：$\text{dp}[i-1][1] + x$
   • 状态 2 $\to$ 状态 2：延续之前已经结束魔法的状态：$\text{dp}[i-1][2] + x$
   • 新起点 $\to$ 状态 2：魔法区间在当前子数组之前就已经结束（等价于魔法作用于空区间，或者作用于子数组左侧，不影响当前子数组）：$0 + x$ $$\text{dp}[i][2] = \max(\text{dp}[i-1][1], \text{dp}[i-1][2], 0) + x$$

初始化与答案计算

• 由于要求子数组非空，我们将整个 dp 数组初始化为极小值（如 -inf）。
• 初始化边界 dp[0][0] = 0。
• 因为魔法操作是可选的（可以施展至多一次，也可以不施展），所以最终的最大和子数组可以结束在任何一个状态：
  • 结束在状态 0，表示完全不进行乘法操作；
  • 结束在状态 1，表示子数组的尾部仍在进行乘法操作；
  • 结束在状态 2，表示子数组的尾部在乘法操作结束后延伸。
• 因此，最终的答案是所有位置上、所有状态下的最大值。即对所有的 $\max(\text{dp}[i][0], \text{dp}[i][1], \text{dp}[i][2])$ 取全局最大值。

三、代码实现

#include <bits/stdc++.h>

using namespace std;
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"

using ll = long long;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const int N = 2e5 + 10, M = 20, INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, k, a[N];
ll dp[N][3]; // dp[i][j] 表示以 i 结尾，处于状态 j 的最大子数组和

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 初始化为极小值，防止从非法状态转移
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0; // 边界情况
    ll ans = -inf;

    for (int i = 1; i <= n; i++) {
        ll x = a[i];

        // 状态 0：未开始施加魔法，当前元素正常累加
        dp[i][0] = max(dp[i - 1][0], 0ll) + x;

        // 状态 1：正在施加魔法，当前元素乘以系数 k
        // 可由：状态 0 转移而来（开始魔法）、状态 1 转移而来（保持魔法）、或者作为子数组新起点直接进入状态 1
        dp[i][1] = max({ dp[i - 1][0], dp[i - 1][1], 0ll }) + x * k;

        // 状态 2：魔法已结束，当前元素正常累加
        // 可由：状态 1 转移而来（结束魔法）、状态 2 转移而来（保持结束状态）、或者作为新起点直接进入状态 2
        dp[i][2] = max({ dp[i - 1][1], dp[i - 1][2], 0ll }) + x;

        // 由于魔法施展是可选的，最大和子数组可能结束于状态 0、状态 1 或状态 2 中的任意一种
        ans = max({ ans, dp[i][0], dp[i][1], dp[i][2] });
    }
    cout << ans;
}

int main() {
    fast;
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

四、复杂度分析

• 时间复杂度：$O(n)$。我们仅需对长度为 $n$ 的数组进行一次线性扫描。每一次循环中，状态机的状态数是常数（3 个状态），状态转移只涉及常数次比较与算术运算，因此整体时间复杂度与数组长度呈线性关系。
• 空间复杂度：$O(n)$。使用了一个大小为 $n \times 3$ 的二维数组来存储状态机的状态。由于 dp[i] 的状态仅依赖于前一个位置 dp[i-1] 的值，该空间复杂度可以通过滚动变量的方法进一步优化至 $O(1)$。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com