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

这道题到底在问什么

输入

arr = [1,-2,0,3]

输出

4(删掉 -2 得 [1,0,3])

输入

arr = [1,-2,-2,3]

输出

3(直接选 [3],一个都不删)

输入

本节演示 arr = [1,-2,3,-2,4,-1,2]

输出

8

最优解：一步一步想明白

1. 3记住这两行:dp0 是不删的最大子数组,dp1 在它基础上多一维「已经删过一次」,dp1 要么删掉当前元素接 dp0,要么保留当前元素接 dp1。
2. 4这是一张两行七列的 dp 表。上面一行 dp0 记「以这个位置结尾、一个都没删」的最大子数组和,下面一行 dp1 记「以这个位置结尾、已经删过一次」的最大和。列号 0 到 6 对应数组的每个位置。我们从左往右一列一列填,每填好一列就拿这两格去刷新全局答案。最终答案不是某个固定格子,而是整张表里所有数的最大值。
3. 5先填第 0 列,也就是只看第一个数 1。不删的话,以它结尾的最大和就是它自己,dp0[0] = 1。删一次呢?这一段只有它一个元素,删掉就剩空了,题目不允许,所以 dp1[0] 是非法的,用一个极小的哨兵值占位,画面里用空集符号表示。答案先初始化成 dp0[0] = 1。
4. 6来到第 1 列,当前数是 -2。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[0] + -2 = 1 + -2 = -1;要么从它自己重新起一段,得 -2。两者取大,dp0[1] = -1。前面那段还能带来正贡献,接上更好。
5. 7再算删过一次的 dp1。两个来源:第一,把当前的 -2 删掉,那这段就退回到前一格不删的 dp0[0] = 1;第二,保留当前的 -2,说明删除发生在更早,接前一格已删的 dp1[0],也就是 非法。前一格的 dp1 还非法,所以只能走第一种、删掉当前元素。dp1[1] = 1,赢家是「删掉当前的 -2」。
6. 8这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 1,和 dp0[1] = -1、dp1[1] = 1 一起取最大,得 1。没有超过之前的 1,答案保持不变。
7. 9来到第 2 列,当前数是 3。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[1] + 3 = -1 + 3 = 2;要么从它自己重新起一段,得 3。两者取大,dp0[2] = 3。前面那段是个累赘,丢掉、从当前位置重开更好。
8. 10再算删过一次的 dp1。两个来源:第一,把当前的 3 删掉,那这段就退回到前一格不删的 dp0[1] = -1;第二,保留当前的 3,说明删除发生在更早,接前一格已删的 dp1[1],也就是 1 + 3 = 4。两者取大。dp1[2] = 4,赢家是「保留 3、删在更早处」。
9. 11这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 1,和 dp0[2] = 3、dp1[2] = 4 一起取最大,得 4。比之前更大,答案被刷新成 4。
10. 12来到第 3 列,当前数是 -2。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[2] + -2 = 3 + -2 = 1;要么从它自己重新起一段,得 -2。两者取大,dp0[3] = 1。前面那段还能带来正贡献,接上更好。
11. 13再算删过一次的 dp1。两个来源:第一,把当前的 -2 删掉,那这段就退回到前一格不删的 dp0[2] = 3;第二,保留当前的 -2,说明删除发生在更早,接前一格已删的 dp1[2],也就是 4 + -2 = 2。两者取大。dp1[3] = 3,赢家是「删掉当前的 -2」。
12. 14这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 4,和 dp0[3] = 1、dp1[3] = 3 一起取最大,得 4。没有超过之前的 4,答案保持不变。
13. 15来到第 4 列,当前数是 4。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[3] + 4 = 1 + 4 = 5;要么从它自己重新起一段,得 4。两者取大,dp0[4] = 5。前面那段还能带来正贡献,接上更好。
14. 16再算删过一次的 dp1。两个来源:第一,把当前的 4 删掉,那这段就退回到前一格不删的 dp0[3] = 1;第二,保留当前的 4,说明删除发生在更早,接前一格已删的 dp1[3],也就是 3 + 4 = 7。两者取大。dp1[4] = 7,赢家是「保留 4、删在更早处」。
15. 17这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 4,和 dp0[4] = 5、dp1[4] = 7 一起取最大,得 7。比之前更大,答案被刷新成 7。
16. 18来到第 5 列,当前数是 -1。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[4] + -1 = 5 + -1 = 4;要么从它自己重新起一段,得 -1。两者取大,dp0[5] = 4。前面那段还能带来正贡献,接上更好。
17. 19再算删过一次的 dp1。两个来源:第一,把当前的 -1 删掉,那这段就退回到前一格不删的 dp0[4] = 5;第二,保留当前的 -1,说明删除发生在更早,接前一格已删的 dp1[4],也就是 7 + -1 = 6。两者取大。dp1[5] = 6,赢家是「保留 -1、删在更早处」。
18. 20这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 7,和 dp0[5] = 4、dp1[5] = 6 一起取最大,得 7。没有超过之前的 7,答案保持不变。
19. 21来到第 6 列,当前数是 2。先算不删的 dp0:要么把它接到前一格那段后面,得 dp0[5] + 2 = 4 + 2 = 6;要么从它自己重新起一段,得 2。两者取大,dp0[6] = 6。前面那段还能带来正贡献,接上更好。
20. 22再算删过一次的 dp1。两个来源:第一,把当前的 2 删掉,那这段就退回到前一格不删的 dp0[5] = 4;第二,保留当前的 2,说明删除发生在更早,接前一格已删的 dp1[5],也就是 6 + 2 = 8。两者取大。dp1[6] = 8,赢家是「保留 2、删在更早处」。
21. 23这一列两格都算好了,拿它们去刷新全局答案。原来的 ans 是 7,和 dp0[6] = 6、dp1[6] = 8 一起取最大,得 8。比之前更大,答案被刷新成 8。
22. 24整张表填满了,所有 dp0、dp1 里最大的是 dp1[6] = 8,这就是答案 8。顺着它倒推:它来自保留末尾的 2、再往前一路保留,删除其实发生在那个 -2 上,把原来的 [3,-2,4,-1,2] 删掉中间的 -2,接成 [3,4,-1,2],和正好是 8。一个负数卡在两段正数中间,删掉它把左右接通,这就是删除带来的收益。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问