页面加载中…
P4201. 分割数组的最大差值
简单通过率 78% · 提交 373 · 通过 290
100分前缀和2025A枚举
改编自华为 OD 机考真题方向 · 100分 / 前缀和类型 · 难度：简单
小慕正在处理一个由若干整数组成的数组nums，他可以在数组内的任意位置进行分割，将该数组分割成两个（即左数组和右数组），分别对子数组求和得到两个值，并计算这两个值的差值。小慕想要知道，在所有可能的分割方案中，差值的最大值是多少。
这类题属于华为 OD 机考真题方向中「100分 / 前缀和」方向的高频题型，通常考察对「100分 / 前缀和」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行输入数组中元素个数n，1 < n <= 100000
第二行输入数字序列，以空格进行分隔，数字取值为4字节整数
输出描述
输出差值的最大取值
示例
示例 1
输入示例
6 1 -2 3 4 -9 7
输出示例
10
说明：
将数组nums 划分为两个非空数组的可行方案有： 左数组 = [1] 且 右数组 = [-2, 3, 4, -9, 7]，和的差值 = |1 - 3|=2 左数组 = [1, -2] 且 右数组 = [3, 4, -9, 7]，和的差值 = |-1 - 5|=6 左数组 = [1, -2, 3, 1] 且 右数组 = [4, -9, 7]，和的差值 = |2 - 2|=0 左数组 = [1, -2, 3, 4] 且 右数组 = [-9, 7]，和的差值 = |6 - (-2)| = 8 左数组 = [1, -2, 3, 4, -9] 且 右数组 = [7]，和的差值 = |-3 - 7| = 10 最大的差值为10
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
解题思路
暴力解法
遍历每一个分割位置，并对左数组和右数组分别调用 sum() 进行求和。该解法的时间复杂度为 O(N^2)，无法通过所有用例。
优化解法
本题的解法类似于 【前缀和】2023B-阿里巴巴找黄金宝箱(1)。应该维护数组的前缀和，在遍历每一个位置 i 时，分别更新 left_sum 和 right_sum，再进行答案的更新。这样的时间复杂度可以降低到 O(N)。
思路展开
这份代码把「枚举分割点 + 分别求两边的和」压缩成了一次线性扫描。关键变量有三个：left_sum 表示当前分割方案下左数组的和，初始为 0；right_sum 表示右数组的和，初始为整个数组的总和 sum(nums)；ans 记录目前见过的最大差值。 循环从左到右遍历 nums 中除最后一个以外的每个元素 num：把 num 从右半部分「挪到」左半部分，即执行 left_sum += num 和 right_sum -= num。这样循环进行到第 i 轮结束时，left_sum 恰好是前 i+1 个元素的和，right_sum 恰好是剩余元素的和，正好对应「在第 i+1 个元素之后切一刀」的分割方案。每挪一个元素只需两次加减，避免了暴力解法里每个分割点都重新调用 sum() 的重复计算，这正是前缀和思想的增量写法。 每一轮用 abs(left_sum - right_sum) 计算当前方案两段和之差的绝对值，并用 max 更新 ans。由于循环恰好覆盖全部 n-1 个合法分割位置，且每个位置的 left_sum、right_sum 都被精确维护，遍历结束时 ans 即所有分割方案中的最大差值。
边界与注意事项
- 两个子数组都必须非空：代码遍历的是 nums[:-1]（C++ 版为 i < n-1），最后一个元素永远留在右数组，保证右边至少一个元素；而循环从第一个元素开始挪，左数组也至少含一个元素，不会出现空数组的非法分割。
- n = 2 时只有一个分割点，循环只执行一轮，直接得到唯一方案的差值。
- 数组含负数时该写法依然成立：left_sum、right_sum 是逐项精确维护的真实和，abs 取的是两段和之差的绝对值，与分割方向无关。
- ans 初始化为 0，而每轮更新值经过 abs 后必然非负，因此初值不会盖过任何真实方案的结果。
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
