每日算法系列【LeetCode 1186】删除一次得到子数组最大和-阿里云开发者社区

每日算法系列【LeetCode 1186】删除一次得到子数组最大和

2022-06-25 216

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 给你一个整数数组，返回它的某个非空子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。

题目描述

给你一个整数数组，返回它的某个非空子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。

换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

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

示例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^5
-10^4 <= arr[i] <= 10^4

题解

首先回顾一道很相似的题目，也就是求连续子数组的最大值，并不需要删除元素。

代码

c++

classSolution {
public:  
intmaximumSum(vector<int>&arr) {   
intn=arr.size();  
intdp[n];     
dp[0] =arr[0];   
intres=dp[0];      
for (inti=1; i<n; ++i) {    
dp[i] =arr[i] +max(dp[i-1], 0);   
res=max(res, dp[i]);    
        }   
intlast=arr[n-1];  
for (inti=n-2; i>0; --i) {   
res=max(res, dp[i-1]+last); 
last=arr[i] +max(last, 0);  
        }      
returnres;  
    }
};

python

classSolution: 
defmaximumSum(self, arr: List[int]) ->int:   
n=len(arr)    
dp= [arr[0]] *nforiinrange(1, n):  
dp[i] =arr[i] +max(dp[i-1], 0)  
res, last=max(dp), arr[-1]   
foriinrange(n-2, 0, -1):
res=max(res, dp[i-1]+last) 
last=arr[i] +max(last, 0)  
returnres