WordPress博客程序优化,芜湖seo网站优化,顺德建网站,江门网络培训学院1. 题目
给你一个整数数组#xff0c;返回它的某个 非空 子数组#xff08;连续元素#xff09;在执行一次可选的删除操作后#xff0c;所能得到的最大元素总和。
换句话说#xff0c;你可以从原数组中选出一个子数组#xff0c;并可以决定要不要从中删除一个元素…1. 题目
给你一个整数数组返回它的某个 非空 子数组连续元素在执行一次可选的删除操作后所能得到的最大元素总和。
换句话说你可以从原数组中选出一个子数组并可以决定要不要从中删除一个元素只能删一次哦删除后子数组中至少应当有一个元素然后该子数组剩下的元素总和是所有子数组之中最大的。
注意删除一个元素后子数组 不能为空。
示例 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-subarray-sum-with-one-deletion 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i][0]表示到以i位置为结束没有删除过元素最大数组和dp[i][1]表示到以i位置为结束删除过1个元素最大数组和
class Solution {
public:int maximumSum(vectorint arr) {int i, n arr.size(), maxSum INT_MIN;vectorvectorint dp(n, vectorint(2,INT_MIN));dp[0][0] arr[0];//0位置不删除元素最大子序和dp[0][1] 0; //0位置删除元素最大子序和maxSum arr[0];for(i 1; i n; i){// i-1 位置处之前没有删除过i位置处也不删 或者 只有 i 自己dp[i][0] max(arr[i], dp[i-1][0]arr[i]);maxSum max(maxSum, dp[i][0]);// i-1 位置之前删除过i位置处不删 或者 i-1之前没有删删除 i 位置dp[i][1] max(dp[i-1][1]arr[i], dp[i-1][0]);maxSum max(maxSum, dp[i][1]);}return maxSum;}
};164 ms 33.2 MB
