删除一次得到子数组最大和 图解题解

删一个元素，到底在所有子数组里挑什么

给数组 arr，选一段连续子数组，可删掉其中至多一个元素（可删可不删），删完不能空，求其中最大的元素和。答案得兼顾一个都不删、和恰好删一个。arr = [1,-2,0,3] 删掉 -2 得 [1,0,3]、和 4；arr = [1,-2,-2,3] 却别删、选 [3] 更好。

为什么把每个删除位置都试一遍会白算

删哪个元素有 n 种选择（含不删），每定一个还要从头求一遍最大连续子数组和，一层套一层就是 O(n²)（大 O 记号，描述规模变大时运算次数怎么涨），n 到 10^5 就跑不动。慢在每换位置，前面那段最大和都从零重算。

两行 dp 各记什么，dp1 那一维为什么是「删过一次」

开两行 dp，也就是动态规划（以第 i 位结尾、删或不删的最大和记表复用）的表。dp0[i] 记「以第 i 个位置结尾、不删的最大子数组和」，就是经典最大子数组（LeetCode 53 的 Kadane：每步在「接前段」和「另起一段」里挑大）。dp1[i] 在 dp0 上多挂一维「已删过一次」，记「以第 i 个位置结尾、恰好删过一个元素的最大和」。dp0、dp1 是两个状态（状态 = 描述当前一步局面的量），答案是两行里的最大值。

dp1 每格为什么在「删当前」和「留当前」两条里取大

dp0 就是 Kadane 那条老式子。新东西在 dp1 的转移（转移 = 由前一格答案推出当前格的式子）：已删过一次的最大和有两条来路。一是删的正好是当前 arr[i]，删完就退回前一格「还没删」的 dp0[i-1]——等于拿前面不删的一段跳过当前接上；二是当前 arr[i] 留着、删除在更早，接前一格「已删过」的 dp1[i-1] 再加 arr[i]。取大：dp1[i] = max(dp0[i-1], dp1[i-1] + arr[i])。dp1[0] 非法（删完为空），拿极小哨兵（哨兵=比任何真实和都小的不可能标记）兜住、别当 0。

拿 [1,-2,3,-2,4,-1,2] 把两行 dp 填到 8

拿题面演示的 arr = [1,-2,3,-2,4,-1,2] 填一遍。dp0 一路 Kadane 扫出 1、-1、3、1、5、4、6。dp1 逐格取两条来路的大者：dp1[1]=max(1, 非法)=1；dp1[2]=max(-1, 1+3)=4；dp1[3]=max(3, 4-2)=3；dp1[4]=max(1, 3+4)=7；dp1[5]=max(5, 7-1)=6；dp1[6]=max(4, 6+2)=8。两行最大 dp1[6]=8 即答案：删掉 [3,-2,4,-1,2] 中间的 -2、接成 [3,4,-1,2]。

dp1[0] 当成 0，全负数组的答案为什么会凭空变大

dp1[0] 是「一个元素还要删」，删完为空、非法。图省事写成 0 就出事：arr 全为负时答案本该是最大的负数，可 dp1[0]=0 会顺着转移把 0 一路抬上去，答案凭空变大。另一处：dp1「删当前」接 dp0[i-1] 而非 dp1[i-1]，接错就成删两次。两行各扫一遍、每格常数运算，时间 O(n)；每格只用前一格，两个滚动变量（只留最近一格）轮替，空间压到 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        left = [0] * n
        right = [0] * n
        s = 0
        for i, x in enumerate(arr):
            s = max(s, 0) + x
            left[i] = s
        s = 0
        for i in range(n - 1, -1, -1):
            s = max(s, 0) + arr[i]
            right[i] = s
        ans = max(left)
        for i in range(1, n - 1):
            ans = max(ans, left[i - 1] + right[i + 1])
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size();
        int left[n];
        int right[n];
        for (int i = 0, s = 0; i < n; ++i) {
            s = max(s, 0) + arr[i];
            left[i] = s;
        }
        for (int i = n - 1, s = 0; ~i; --i) {
            s = max(s, 0) + arr[i];
            right[i] = s;
        }
        int ans = *max_element(left, left + n);
        for (int i = 1; i < n - 1; ++i) {
            ans = max(ans, left[i - 1] + right[i + 1]);
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int ans = -(1 << 30);
        for (int i = 0, s = 0; i < n; ++i) {
            s = Math.max(s, 0) + arr[i];
            left[i] = s;
            ans = Math.max(ans, left[i]);
        }
        for (int i = n - 1, s = 0; i >= 0; --i) {
            s = Math.max(s, 0) + arr[i];
            right[i] = s;
        }
        for (int i = 1; i < n - 1; ++i) {
            ans = Math.max(ans, left[i - 1] + right[i + 1]);
        }
        return ans;
    }
}