你好！我是你的OI信息学奥赛教练。今天我们将深入探讨一类非常经典且极其重要的动态规划模型——连续子数组优化问题（Subarray Optimization with Dynamic Programming）。

为了让你在NOI/CSP等竞赛中遇到此类问题时能举一反三，我不会直接给你贴代码，而是带你还原推导过程，把知识嚼碎了咽下去。我们将原教程的内容整合成一道“NOI风格”的综合性练习题。

---

第一部分：NOI风格题目描述

题目名称：连续子数组优化综合（Subarray Fundamentals & Variations）

【题目描述】 给定一个长度为 $n$ 的整数序列 $A = (a_1, a_2, \dots, a_n)$。请你解决以下五个独立的子任务（Subtasks）：

1. 最大子数组和（Max Subarray Sum）： 找到一个连续子数组，使其元素之和最大。
2. 最大子数组乘积（Max Subarray Product）： 找到一个连续子数组，使其元素乘积最大。
3. 环形最大子数组和（Max Circular Subarray Sum）： 假设序列首尾相连形成环状，找到其中和最大的连续子数组。
4. 最多删除一次的最大子数组和（Max Sum with At Most One Deletion）： 你可以选择在连续子数组中最多删除一个元素，求操作后的最大子数组和。
5. 最长湍流子数组（Longest Turbulent Subarray）： 找到最长的连续子数组，满足相邻元素的比较符号（< 和 >）交替出现。

注意：子数组（Subarray）必须是原数组中一段连续（Contiguous）的元素，这与子序列（Subsequence，可不连续）不同。

【输入格式】 第一行包含一个整数 $n$（$1 \le n \le 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^4 \le a_i \le 10^4$）。

【输出格式】 共五行，分别输出上述五个子任务的答案。

【样例输入】

9
-2 1 -3 4 -1 2 1 -5 4

【样例输出说明】 任务1输出提示：最大和子数组为 4, -1, 2, 1，结果为 6。 (其余任务由于样例数据局限，此处不展开，将在推导中给出专有小样例)

---

第二部分：预备知识点总结

在草稿纸上动手前，你的大脑“武器库”里需要准备好以下弹药：

1. 概念辨析： 严格区分 子数组（Subarray，连续） 与 子序列（Subsequence，保持相对顺序但不一定连续）。
2. DP的黄金法则（The Golden Rule）： 定义状态时，必须强制包含当前考察的末尾元素。即 dp[i] 表示**“以索引 i 恰好结尾的最优子数组”**。
3. 空间压缩技术（Rolling Variables）： 掌握如何将一维 $O(n)$ 的状态数组压缩为 $O(1)$ 的几个标量变量（常说的“滚动数组”极简版）。
4. 分类讨论思想： 遇到负数乘积、环形跨越、删除操作时，学会引入额外状态（State Extension）或逆向思维（Inversion Trick）。
5. 算法选型雷达： 能够区分何时用 单点DP（当前状态仅依赖上一个状态）、滑动窗口（满足特定条件下的区间伸缩）以及 前缀和（静态区间的快速求和）。

---

第三部分：读题与理解题意的关键词

在考场上读题时，你的眼睛应该像雷达一样扫过这些关键词，它们直接决定了你的算法走向：

• 关键词：“连续”（Contiguous / Subarray）
  • 破题点： 绝大数情况下，这意味着你要用“以第 $i$ 个元素结尾”作为DP状态，或者考虑滑动窗口。
• 关键词：“最大 / 最长 / 最优”
  • 破题点： 最优化问题，几乎可以确定是DP或贪心。
• 关键词：“存在负数” 且与 “乘积” 结合
  • 破题点： 负负得正！普通的最大值传递会失效，必须同时维护最大值和最小值。
• 关键词：“环形”（Circular）
  • 破题点： 包含两种情况：要么是没有跨越边界的“常规线性子数组”，要么是跨越了边界的“缠绕（Wrapped）子数组”。
• 关键词：“允许改变 / 删除最多 $k$ 个元素”
  • 破题点： 状态机模型。你需要“扩展状态（State Extension）”，加一维维度 dp[i][k] 来记录条件使用的次数。

---

第四部分：草稿纸上的启发式与图形式推导（核心教学）

假设现在我们在考场上，只有纸和笔。对于任务1（最大子数组和），跟着我一步步画图思考：

1. 状态定义（寻找黄金法则）

如果你试图让 dp[i] 表示“前 $i$ 个元素中的全局最大和”，当你递推到 $i+1$ 时，你会发现接不上了！因为如果你不知道前 $i$ 个元素的最大和是不是恰好贴着 $i$ 的边缘，你根本无法把 $nums[i+1]$ 连续地拼上去。 写在草稿纸上的铁律：令 localMax 为强制以当前元素 $nums[i]$ 结尾的最大子数组和。

2. 状态转移（本地选择）

当你走到 $nums[i]$ 面前，你只有两个选择（画个岔路口）：

• 选择A（带着历史包袱）： 把 $nums[i]$ 接在之前的最优子数组后面。价值 = 上一轮的 localMax + nums[i]。
• 选择B（断尾求生，重新开始）： 嫌弃前面的和太小（甚至是负数，拖累了自己），决定自己单干。价值 = nums[i]。

因此，转移方程跃然纸上：$LocalMax_i = \max(nums[i], LocalMax_{i-1} + nums[i])$

3. 空间优化分析与伪代码流程图 (Mermaid)

注意观察上面的方程，计算当期状态只依赖上一步的状态。我们在数组里开辟 $O(n)$ 的空间（就像一页纸只写一个字）太浪费了（Trimming the Fat）。 我们只需要两个变量：local_max 和 global_max。

请看下面的状态流转伪代码（注意看我是如何使用临时变量或滚动更新的）：

graph TD
    A("开始: 输入数组 nums, 长度为 n") --> B{"判断: 数组为空?"}
    B -- 是 --> C("返回 0")
    B -- 否 --> D("初始化: local_max = nums[0]<br>global_max = nums[0]<br>i = 1")
    D --> E{"循环条件: i < n ?"}
    E -- 是 --> F("取出当前元素: num = nums[i]")
    F --> G("局部最优决策 (状态转移):<br>local_max = max(num, local_max + num)")
    G --> H("更新全局最优:<br>global_max = max(global_max, local_max)")
    H --> I("i = i + 1")
    I --> E
    E -- 否 --> J("结束循环")
    J --> K("返回 global_max")

复杂度分析：

• 时间复杂度： 我们只遍历了数组一次（One pass），毫无疑问是 $O(n)$。
• 空间复杂度优化建议： 从原先分配 vector<int> dp(n) 的 $O(n)$，因为每次只依赖前一个状态，压缩为两个标量变量，成功降维到 $O(1)$。这是NOI考察基本功的常见得分点。

---

第五部分：高阶变体思路提示（点到为止）

现在，针对剩下的任务，我给你抛几个问题，你顺着我的思路想，千万不要直接去写代码，先在纸上写出状态方程！

💡 任务2：最大乘积（当规则改变）

• 提示： 遇到负数怎么办？一个极小的负数乘积（比如 -100），只要再乘一个负数（比如 -5），瞬间暴涨成最大的正数（500）。
• 启发： 所以你不能只记录最大值。你必须准备两个DP状态：curr_max 和 curr_min。
• 陷阱： 更新 curr_max 时，是不是可能用到旧的 curr_min？如果你先覆盖了 curr_max，再去算 curr_min，数据是不是被污染了？（想想怎么用 temp 变量来存旧值，或者在C++里用 std::max({a, b, c}) 同步计算）。

💡 任务3：环形数组（破环成链与逆向思维）

• 提示： 环形的最优解只存在两种物理形态：
  1. 老老实实呆在中间，没有跨越首尾（这不就是任务1吗？最大线性和）。
  2. 跨越了首尾边界（The Inversion Trick）。
• 启发： 跨越首尾的子数组，它的补集是什么？必定是中间一段连续的、被抛弃的子数组。要想让跨越首尾的和最大，那么中间那段被抛弃的和必须最小！
• 公式推导： 最大跨越和 = 序列总和 (Total Sum) - 最小连续子数组和 (Min Linear Sum)。
• 极端边界预警（Edge Case）： 如果数组全是负数（例如 [-1, -2, -3]），总和是 -6，最小子数组和也是 -6，一减变成了 0！但这相当于你把整个数组都“抛弃”了（空集），题目允许吗？这种情况该直接返回什么？

💡 任务4：最多删除一次（扩展状态维度）

• 提示： 走到第 $i$ 个元素时，如果只是 dp[i]，你知道前面有没有用过删除特权吗？不知道。状态缺失了！
• 启发： 我们需要给状态加个“标识（Flag）”。设 dp[i][0] 为一次没删过的最大和，dp[i][1] 为已经删过一次的最大和。
• 推导岔路口：
  • 算 dp[i][0] 时，这和普通的 Kadane 算法完全一样。
  • 算 dp[i][1] 时（包含 $i$ 为结尾），有两种情况：要么是历史已经删过别人了，当前 $nums[i]$ 必须加上；要么刚好删除就是当前的 $nums[i]$，那么你能接上的最优历史包袱是谁？是上一步的什么状态？

💡 任务5：最长湍流（条件随比较符翻转）

• 提示： 如果上一对数字是 <，这一对必须是 >，连续性才得以维持。
• 启发： 状态需要记录波峰和波谷。维护两个变量：up（以升序结尾的最长长度）和 down（以降序结尾的最长长度）。
• 思考流： 读到 $nums[i] > nums[i-1]$ 时，哪个状态可以延长？(up = down + 1)。哪个状态被破坏需要重置为 1？(down = 1)。如果是相等的情况呢？

---

教练的最后叮嘱（Choosing the Right Tool）： 在你日后做题时，如何判断用我们今天学的 单状态连续DP（One Subarray DP） 还是 滑动窗口 或 前缀和？ 记住这句话：

• 如果是静态区间查询或者求具体某个和的出现 $\rightarrow$ 想想 前缀和 (Prefix Sum)。
• 如果是寻找满足某种整体条件的区间（比如和刚好大于 $k$，包含 $m$ 个不同元素），区间可以像毛毛虫一样伸缩 $\rightarrow$ 上 滑动窗口 (Sliding Window)。
• 如果当前位置的最优解，必须且仅依赖于它紧挨着的前一个位置的局部最优选择 $\rightarrow$ 毫不犹豫，掏出今天的 One Subarray DP 模板！

现在，带着这些提示，去草稿纸上把任务2到任务5的状态转移方程写出来吧！有问题随时叫我。

---

请提交子问题代码：

太棒了！将大综合题拆解为5个独立的专项训练，是非常科学的备考策略。这样我们可以针对每一种“连续子数组DP（One Subarray DP）”的变体进行深度刻意练习。

作为你的教练，接下来我将为你呈现这5道独立题目的完整题面、预备知识点、草稿纸推导过程以及无代码纯逻辑的流程图。

请准备好草稿纸，我们开始通关！

---

题目一：基础模型 —— 最大子数组和（Maximum Subarray Sum）

【题目描述】 给定一个包含 $n$ 个整数的序列 $A = (a_1, a_2, \dots, a_n)$。请你找到一个连续子数组，使其元素之和最大，并输出该最大和。 注：子数组至少包含一个元素。

【输入格式】 第一行包含一个整数 $n$（$1 \le n \le 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^4 \le a_i \le 10^4$）。

【输出格式】 输出一个整数，表示最大连续子数组的和。

【样例输入】

9
-2 1 -3 4 -1 2 1 -5 4

【样例输出】

6

【样例说明】 连续子数组 [4, -1, 2, 1] 的和最大，为 6。

💡 教练草稿纸推导与讲解

1. 读题关键词与预备知识：

• 连续（Contiguous / Subarray）： 严格区分于“子序列（Subsequence）”。连续意味着我们必须采用“以当前元素为结尾”的状态定义。
• DP的黄金法则（The Golden Rule）： 定义 dp[i] 为恰好以索引 $i$ 结尾的最优子数组和。
• 选择工具（Choosing the Right Tool）： 为什么不用滑动窗口？因为这里没有限制具体的条件（比如和必须等于K），而是求极值，且第 $i$ 步的最优解完全可以由第 $i-1$ 步构建。

2. 启发式推导（Local vs Global）：

• 走到第 $i$ 个数时，局部选择（The Local Choice）：前面的子数组和如果是正的，加上它我会变得更大；如果是负的（比如样例里的 -2），加上它只会拖累我，不如我重新开始（Start a new subarray）。
• 转移方程：当前局部最大 = max(当前元素, 上一个局部最大 + 当前元素)。
• 全局最大（Global Maximum）： 局部最优的最后一个元素不一定是全局最优，必须用一个变量随时打擂台记录全局最大值。

3. 时空复杂度与优化建议（Trimming the Fat）：

• 时间复杂度：只需遍历一次数组，为 $O(n)$。
• 空间复杂度：由于 dp[i] 只依赖 dp[i-1]，我们不需要开辟 $O(n)$ 的数组。使用**滚动变量（Rolling Variable）**技术，用一个 local_max 代替整个数组，空间复杂度降至 $O(1)$。

4. 逻辑流程图（C++14 伪代码思路）：

graph TD
    Start("开始") --> Init("初始化:<br>local_max = a_1<br>global_max = a_1")
    Init --> LoopStart{"遍历序列从 i=2 到 n"}
    LoopStart -- 是 --> Calc("局部决策:<br>local_max = max(a_i, local_max + a_i)")
    Calc --> Update("全局打擂台:<br>global_max = max(global_max, local_max)")
    Update --> LoopStart
    LoopStart -- 遍历结束 --> End("输出 global_max")

---

教练总结语： 通过这5道题，你有没有发现它们底层的核心哲学（Core Philosophy）完全一样？ 永远从“以当前索引 $i$ 结尾”的视角去思考子问题！ 遇到复杂情况，不要慌，要么维护多个状态（最大/最小，升/降），要么增加维度（删与不删），要么运用逆向数学转换（环形变线性）。把这种思路刻在肌肉记忆里，NOI赛场上此类题将成为你的送分题！