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

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

题解 1 - cpp

• 编辑时间：2023-06-27
• 执行用时：32ms
• 内存消耗：22.6MB
• 编程语言：cpp
• 解法介绍：dp[i]表示以arr[i]为结尾的删0个和1个时的最大值。

#define MIN -0x3f3f3f3f
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size(), dp0 = MIN, dp1 = MIN, res = MIN;
        for (int i = 0; i < n; i++) {
            dp1 = max(dp0, dp1 + arr[i]);
            dp0 = max(dp0, 0) + arr[i];
            res = max(res, max(dp0, dp1));
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-06-27
• 执行用时：104ms
• 内存消耗：24.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        dp0 = dp1 = res = -inf
        for num in arr:
            dp1 = max(dp0, dp1 + num)
            dp0 = max(dp0, 0) + num
            res = max(res, max(dp0, dp1))
        return res

题解 3 - rust

• 编辑时间：2023-06-27
• 执行用时：8ms
• 内存消耗：3MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn maximum_sum(arr: Vec<i32>) -> i32 {
        use std::cmp::max;
        let (mut dp0, mut dp1, mut res) = (-0x3f3f3f3f, -0x3f3f3f3f, -0x3f3f3f3f);
        for num in arr {
            dp1 = max(dp0, dp1 + num);
            dp0 = max(dp0, 0) + num;
            res = max(res, max(dp0, dp1));
        }
        res
    }
}

题解 4 - python

• 编辑时间：2024-07-21
• 执行用时：110ms
• 内存消耗：40.88MB
• 编程语言：python
• 解法介绍：dp[i][j]表示以i为结尾的数组，当前已经删除了j个元素时的最大和。

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = arr[0]
        dp[0][1] = 0
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], 0) + arr[i]
            dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0])
        return max([v for item in dp[1:] for v in item], default = arr[0])