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

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

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

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

示例 1：

输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。

示例 2：

输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。

示例 3：

输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

提示：

1 <= arr.length <= 10⁵
-10⁴ <= arr[i] <= 10⁴

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maximumSum(vector<int>& arr) { } };

javascript 解法, 执行用时: 66 ms, 内存消耗: 52.7 MB, 提交时间: 2024-07-21 10:49:21

/**
 * @param {number[]} arr
 * @return {number}
 */
var maximumSum = function(arr) {
    let dp0 = arr[0], dp1 = 0, res = arr[0];
    for (let i = 1; i < arr.length; i++) {
        dp1 = Math.max(dp0, dp1 + arr[i]);
        dp0 = Math.max(dp0, 0) + arr[i];
        res = Math.max(res, Math.max(dp0, dp1));
    }
    return res;
};

cpp 解法, 执行用时: 20 ms, 内存消耗: 22.7 MB, 提交时间: 2023-06-27 09:28:54

class Solution {
public:
    int maximumSum(vector<int> &arr) {
        int ans = INT_MIN / 2, f0 = ans, f1 = ans;
        for (int x: arr) {
            f1 = max(f1 + x, f0);
            f0 = max(f0, 0) + x;
            ans = max(ans, max(f0, f1));
        }
        return ans;
    }
};

java 解法, 执行用时: 5 ms, 内存消耗: 50.5 MB, 提交时间: 2023-06-27 09:28:40

class Solution {
    public int maximumSum(int[] arr) {
        int ans = Integer.MIN_VALUE / 2, f0 = ans, f1 = ans;
        for (int x : arr) {
            f1 = Math.max(f1 + x, f0);
            f0 = Math.max(f0, 0) + x;
            ans = Math.max(ans, Math.max(f0, f1));
        }
        return ans;
    }
}

python3 解法, 执行用时: 92 ms, 内存消耗: 24.1 MB, 提交时间: 2023-06-27 09:28:14

# 空间优化
# f[1] = max(f[1]+arr[i], f[0])
# f[0] = max(f[0], 0) + arr[i]
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        ans = f0 = f1 = -inf
        for x in arr:
            f1 = max(f1 + x, f0)  # 注：改用 if 比大小会更快 
            f0 = max(f0, 0) + x
            ans = max(ans, f0, f1)
        return ans

golang 解法, 执行用时: 36 ms, 内存消耗: 7.5 MB, 提交时间: 2023-06-27 09:27:26

// 空间优化，f[1] = max(f[1]+arr[i], f[0]), f[0] = max(f[0], 0) + arr[i]
func maximumSum(arr []int) int {
    ans := math.MinInt / 2
    f0, f1 := ans, ans
    for _, x := range arr {
        f1 = max(f1+x, f0)
        f0 = max(f0, 0) + x
        ans = max(ans, max(f0, f1))
    }
    return ans
}

func max(a, b int) int { if b > a { return b }; return a }

golang 解法, 执行用时: 44 ms, 内存消耗: 8 MB, 提交时间: 2023-06-27 09:26:00

func maximumSum(arr []int) int {
    ans := math.MinInt
    f := make([][2]int, len(arr)+1)
    f[0] = [2]int{math.MinInt / 2, math.MinInt / 2} // 除 2 防止负数相加溢出
    for i, x := range arr {
        f[i+1][0] = max(f[i][0], 0) + x
        f[i+1][1] = max(f[i][1]+x, f[i][0])
        ans = max(ans, max(f[i+1][0], f[i+1][1]))
    }
    return ans
}

func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 60 ms, 内存消耗: 33.3 MB, 提交时间: 2023-06-27 09:25:40

class Solution {
public:
    int maximumSum(vector<int> &arr) {
        int ans = INT_MIN, n = arr.size();
        vector<vector<int>> f(n + 1, vector<int>(2, INT_MIN / 2)); // 除 2 防止负数相加溢出
        for (int i = 0; i < n; i++) {
            f[i + 1][0] = max(f[i][0], 0) + arr[i];
            f[i + 1][1] = max(f[i][1] + arr[i], f[i][0]);
            ans = max(ans, max(f[i + 1][0], f[i + 1][1]));
        }
        return ans;
    }
};

java 解法, 执行用时: 11 ms, 内存消耗: 50.2 MB, 提交时间: 2023-06-27 09:25:20

class Solution {
    public int maximumSum(int[] arr) {
        int ans = Integer.MIN_VALUE, n = arr.length;
        var f = new int[n + 1][2];
        Arrays.fill(f[0], Integer.MIN_VALUE / 2); // 除 2 防止负数相加溢出
        for (int i = 0; i < n; i++) {
            f[i + 1][0] = Math.max(f[i][0], 0) + arr[i];
            f[i + 1][1] = Math.max(f[i][1] + arr[i], f[i][0]);
            ans = Math.max(ans, Math.max(f[i + 1][0], f[i + 1][1]));
        }
        return ans;
    }
}

python3 解法, 执行用时: 164 ms, 内存消耗: 37.2 MB, 提交时间: 2023-06-27 09:25:01

'''
递推
dfs(i, j) => f[i][j]
'''
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        f = [[-inf] * 2] + [[0, 0] for _ in arr]
        for i, x in enumerate(arr):
            f[i + 1][0] = max(f[i][0], 0) + x
            f[i + 1][1] = max(f[i][1] + x, f[i][0])
        return max(max(r) for r in f)

golang 解法, 执行用时: 20 ms, 内存消耗: 9.4 MB, 提交时间: 2023-06-27 09:24:01

func maximumSum(arr []int) int {
    memo := make([][2]int, len(arr))
    for i := range memo {
        memo[i] = [2]int{math.MinInt, math.MinInt}
    }
    var dfs func(int, int) int
    dfs = func(i, j int) (res int) {
        if i < 0 {
            return math.MinInt / 2 // 除 2 防止负数相加溢出
        }
        p := &memo[i][j]
        if *p != math.MinInt { // 之前计算过
            return *p
        }
        defer func() { *p = res }() // 记忆化
        if j == 0 {
            return max(dfs(i-1, 0), 0) + arr[i]
        }
        return max(dfs(i-1, 1)+arr[i], dfs(i-1, 0))
    }
    ans := math.MinInt
    for i := range arr {
        ans = max(ans, max(dfs(i, 0), dfs(i, 1)))
    }
    return ans
}

func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 60 ms, 内存消耗: 33.4 MB, 提交时间: 2023-06-27 09:23:42

class Solution {
public:
    int maximumSum(vector<int> &arr) {
        int ans = INT_MIN, n = arr.size();
        vector<vector<int>> memo(n + 1, vector<int>(2, INT_MIN));
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i < 0) return INT_MIN / 2; // 除 2 防止负数相加溢出
            int &res = memo[i][j]; // 注意这里是引用
            if (res != INT_MIN) return res; // 之前计算过
            if (j == 0) return res = max(dfs(i - 1, 0), 0) + arr[i];
            return res = max(dfs(i - 1, 1) + arr[i], dfs(i - 1, 0));
        };
        for (int i = 0; i < n; i++)
            ans = max(ans, max(dfs(i, 0), dfs(i, 1)));
        return ans;
    }
};

java 解法, 执行用时: 7 ms, 内存消耗: 50 MB, 提交时间: 2023-06-27 09:23:22

class Solution {
    private int[] arr;
    private int[][] memo;

    public int maximumSum(int[] arr) {
        this.arr = arr;
        int ans = Integer.MIN_VALUE, n = arr.length;
        memo = new int[n][2];
        for (int i = 0; i < n; i++)
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        for (int i = 0; i < n; i++)
            ans = Math.max(ans, Math.max(dfs(i, 0), dfs(i, 1)));
        return ans;
    }

    private int dfs(int i, int j) {
        if (i < 0) return Integer.MIN_VALUE / 2; // 除 2 防止负数相加溢出
        if (memo[i][j] != Integer.MIN_VALUE) return memo[i][j]; // 之前计算过
        if (j == 0) return memo[i][j] = Math.max(dfs(i - 1, 0), 0) + arr[i];
        return memo[i][j] = Math.max(dfs(i - 1, 1) + arr[i], dfs(i - 1, 0));
    }
}

python3 解法, 执行用时: 212 ms, 内存消耗: 78.7 MB, 提交时间: 2023-06-27 09:22:59

'''
dfs(i, j): 枚举子数组右端点 i，以及是否需要删除数字 j=0,1，取所有结果的最大值，作为答案。

不选arr[i]左边的数：dfs(i, 0) = arr[i]
选arr[i]左边的数：dfs(i, 0) = dfs(i-1, 0) + arr[i]

不删除arr[i]：dfs(i, 1) = dfs(i-1, 1) + arr[i]
删除arr[i]：dfs(i, 1) = dfs(i-1, 0)

dfs(i, 0) = max(dfs(i-1, 0), 0) + arr[i]
dfs(i, 1) = max(dfs(i-1, 1) + arr[i], dfs(i-1, 0))
'''
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        @cache  # 记忆化搜索
        def dfs(i: int, j: int) -> int:
            if i < 0: return -inf  # 子数组至少要有一个数，不合法
            if j == 0: return max(dfs(i - 1, 0), 0) + arr[i]
            return max(dfs(i - 1, 1) + arr[i], dfs(i - 1, 0))
        return max(max(dfs(i, 0), dfs(i, 1)) for i in range(len(arr)))

上一题

下一题

详情