从零实现 Java 滑动窗口：「删除子数组的最大得分」的解题思路

问题描述

给定一个正整数数组，要求删除一个连续子数组（长度至少为1），使得剩余元素的和最大。剩余元素必须非空，且保持原始顺序。这个最大和被称为"删除子数组的最大得分"。

核心思路

通过分析发现：最大得分 = 数组总和 - 数组最小值。这是因为：

1. 数组元素均为正整数
2. 删除单个最小值元素可使剩余和最大化
3. 删除任意长度的子数组，剩余和都不可能大于总和 - 最小值

数学证明

设数组为 $A = [a_0, a_1, \dots, a_{n-1}]$，总和为： $$S = \sum_{k=0}^{n-1} a_k$$ 最小值为： $$m = \min_{0 \leq i < n} a_i$$ 则最大得分恒等于： $$S - m$$

Java实现

public int maximumScore(int[] nums) {
    if (nums.length == 1) return 0;  // 无法删除
    
    int total = 0;
    int min = Integer.MAX_VALUE;
    
    for (int num : nums) {
        total += num;            // 计算总和
        if (num < min) min = num; // 更新最小值
    }
    return total - min;  // 最大得分
}

复杂度分析

• 时间复杂度：$O(n)$
  仅需一次遍历计算总和和最小值
• 空间复杂度：$O(1)$
  仅使用常数级额外空间

案例验证

1. 示例：[1,2,3,4,5,6,1]

   • 总和 = 22，最小值 = 1
   • 最大得分 = 22 - 1 = 21
   • 实现：删除任意一个"1"（如首位），剩余[2,3,4,5,6,1]或[1,2,3,4,5,6]，和均为21

2. 边界测试：[5,8]

   • 总和 = 13，最小值 = 5
   • 最大得分 = 13 - 5 = 8（删除5，保留8）

3. 性能测试：[10^5个元素]

   • 时间复杂度 $O(n)$，可在毫秒级完成

思维拓展

虽然本题可简化解决，但同类问题变种（如含负数或特殊约束）可能需要滑动窗口。通用解法框架：

1. 计算前缀和与后缀和数组
2. 枚举分割点求最大前缀+后缀组合
3. 时间复杂度 $O(n)$，空间复杂度 $O(n)$

总结

本题通过数学分析转化为求最小值问题，避免复杂算法设计。关键点：

1. 利用正整数特性简化问题
2. 识别"删除最小值即最大化剩余"的核心逻辑
3. 边界处理确保代码健壮性

通过这个实现，我们不仅高效解决了问题，更深化了对数组操作本质的理解——复杂问题往往有简洁优雅的数学解。