JZX轻语：简
LeetCode 1186 - 删除一次得到子数组最大和
发表于2024年07月05日
最大和子数组的变种题目，新增了一个允许删除一个元素的条件。对于最大和子数组，其中以第i个元素结尾的子数组最大和为dp[i] = max(dp[i-1] + nums[i], nums[i])。对于本题，我们可以使用二维n * 2的dp数组，其中dp[i][0]和dp[i][1]分别表示以第i个元素结尾的非空子数组，不删除元素和删除一个元素的情况下的最大和。对于不删除元素的情况，dp[i][0] = max(dp[i-1][0] + nums[i], nums[i])；对于删除一个元素的情况，dp[i][1] = max(dp[i - 1][0], dp2[i-1] + nums[i])(即要么是删除本元素，要么就是不删除本元素，删除的操作在前面的元素)。最终结果即为上述循环中最大的数组值，注意不能取dp[0][1]，因为题目要求子数组非空的。(2024-07-21更新实际上，dp[0][1]是不符合上述的非空子数组要求的，只不过这里为了方便计算，将dp[0][1]设置为初始值0，但不计入结果)
class Solution:
def maximumSum(self, arr: List[int]) -> int:
# dp[i][0]: 以第i个元素结尾的, 没有进行删除操作的子数组最大和
# dp[i][1]: 以第i个元素结尾的, 进行了一次删除操作的子数组最大和
dp = [[0, 0] for _ in range(len(arr))]
dp[0][0] = arr[0]
# 注意这里的ans初始值不能考虑dp[0][1], 因为题目要求子数组是非空的
ans = dp[0][0]
for i in range(1, len(arr)):
dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i])
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + arr[i])
ans = max(ans, dp[i][0], dp[i][1])
return ansC++的做法：
class Solution {
public:
int maximumSum(vector<int>& arr) {
vector<vector<int>> dp(arr.size(), vector<int>(2, 0));
dp[0][1] = 0; dp[0][0] = arr[0];
int ans = arr[0];
for (int i = 1; i < arr.size(); ++i) {
// update dp[i][0]
dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]);
// update dp[i][1]
dp[i][1] = max(
dp[i - 1][0],
dp[i - 1][1] + arr[i]
);
ans = max(ans, max(dp[i][0], dp[i][1]));
}
return ans;
}
};使用滚动dp压缩空间的做法，即只使用两个变量dp0和dp1来表示dp[i][0]和dp[i][1]，可以将空间复杂度降低为O(1)。
class Solution:
def maximumSum(self, arr: List[int]) -> int:
# dp[i][0]: 以第i个元素结尾的, 没有进行删除操作的子数组最大和
# dp[i][1]: 以第i个元素结尾的, 进行了一次删除操作的子数组最大和
dp0, dp1 = arr[0], 0
# 注意这里的ans初始值不能考虑dp[0][1], 因为题目要求子数组是非空的
ans = dp0
for i in range(1, len(arr)):
dp0, dp1 = max(dp0 + arr[i], arr[i]), max(dp0, dp1 + arr[i])
ans = max(ans, dp0, dp1)
return ansC++的滚动dp做法：
class Solution {
public:
int maximumSum(vector<int>& arr) {
int dp1 = 0, dp0 = arr[0];
int ans = arr[0];
for (int i = 1; i < arr.size(); ++i) {
// update dp[i][0]
int new_dp0 = max(dp0 + arr[i], arr[i]);
// update dp[i][1]
int new_dp1 = max(
dp0,
dp1 + arr[i]
);
dp0 = new_dp0; dp1 = new_dp1;
ans = max(ans, max(dp0, dp1));
}
return ans;
}
};