1186. 删除一次得到子数组最大和

Powered by:NEFU AB-IN

Link

1186. 删除一次得到子数组最大和

题意

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组 不能为空。

思路

1. https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/solutions/2314975/shan-chu-yi-ci-de-dao-zi-shu-zu-de-zui-d-o1o9/ 直接dp
2. 最大子数组和
   1. 如果最大值小于0，则返回最大值
   2. 如果最小值大于0，则返回总和
   3. 之后从前和从后求最大子数组和（Kadane’s Algorithm）
      1. dp[i] 表示以第 i 个元素结尾的最大子数组和。
      2. 对于每个元素，更新 dp[i]，它是当前元素本身和当前元素加上前一个子数组最大和 dp[i-1] 的较大值。
   4. 遍历数组，得到这个元素两边的最大子数组和，求最大值即可

代码

'''
Author: NEFU AB-IN
Date: 2024-07-21 20:17:29
FilePath: \LeetCode\1186\1186.py
LastEditTime: 2024-07-21 20:41:45
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        arr = [0, *arr]
        max_, sum_, min_ = -INF, 0, INF

        for i in range(1, n + 1):
            sum_ += arr[i]
            max_ = Math.max(max_, arr[i])
            min_ = Math.min(min_, arr[i])

        if min_ > 0:
            return sum_
        if max_ < 0:
            return max_

        dpl, dpr = Arr.array(0, n + 2), Arr.array(0, n + 2)
        for i in range(1, n + 1):
            dpl[i] = Math.max(arr[i], dpl[i - 1] + arr[i])
        for i in range(n, -1, -1):
            dpr[i] = Math.max(arr[i], dpr[i + 1] + arr[i])

        for i in range(1, n + 1):
            max_ = max(max_, dpl[i - 1] + dpr[i + 1], dpl[i - 1], dpr[i + 1])
        return max_