2023-06-27每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

提示：

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

四、解题代码

class Solution {
public:int maximumSum(vector<int>& arr) {int n = arr.size();int dp[n+5][2];int max0 = arr[0];memset(dp,0,sizeof(dp));if(arr[0] > 0){dp[0][0] = arr[0];dp[0][1] = 0;}else{dp[0][0] = arr[0];dp[1][0] = 0;}for(int i = 1; i < n; ++i){dp[i][0] = max(arr[i] + dp[i-1][0], arr[i]);dp[i][1] = max(dp[i-1][1]+arr[i], dp[i-1][0]);max0 = max(dp[i][0], max0);max0 = max(dp[i][1], max0);}return max0;}
};

五、解题思路

(1) 采用动态规划算法来解决问题