如何优化公司网站,上海网站建设浦东,做企业网站的架构图,电子商务网站建设成本1186. 删除一次得到子数组最大和#xff08;leetcode#xff09;
题目描述 给你一个整数数组#xff0c;返回它的某个 非空 子数组#xff08;连续元素#xff09;在执行一次可选的删除操作后#xff0c;所能得到的最大元素总和。换句话说#xff0c;你可以从原数组中选…1186. 删除一次得到子数组最大和leetcode
题目描述 给你一个整数数组返回它的某个 非空 子数组连续元素在执行一次可选的删除操作后所能得到的最大元素总和。换句话说你可以从原数组中选出一个子数组并可以决定要不要从中删除一个元素只能删一次哦删除后子数组中至少应当有一个元素然后该子数组剩下的元素总和是所有子数组之中最大的。 注意删除一个元素后子数组不能为空。 示例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 a r r . l e n g t h 1 0 5 1 arr.length 10^5 1arr.length105 − 1 0 4 a r r [ i ] 1 0 4 -10^4 arr[i] 10^4 −104arr[i]104 题解1C版本
class Solution {
public:int maximumSum(vectorint arr) {int n arr.size();vectorvectorint dp(n 1, vectorint(2, 0));// dp[i][0]表示以第i个元素结尾且没有执行删除操作所能得到的最大元素总和// dp[i][1]表示以第i个元素结尾且执行了一次删除操作所能得到的最大元素总和int res arr[0];dp[1][0] arr[0];dp[1][1] arr[0]; // 由于子数组不能为空因此只有一个元素时dp[1][1] arr[0]for(int i 2; i n; i){dp[i][0] max(dp[i - 1][0] arr[i - 1], arr[i - 1]);dp[i][1] max(dp[i - 1][1] arr[i - 1], dp[i - 1][0]);res max(res, max(dp[i][0], dp[i][1]));}return res;}
};
