苏三的免费八股文网站：
最近一网友收到一个offer，因为自己在洗澡没有看到，结果过了40分钟hr又把offer给撤回了，关键hr还把他的联系方式给删了，也没办法争取了。
我对这种仅过了40分钟就撤回offer的行为很是不能理解，说明他们也不是真的很缺人，如果真的缺人，也不会在乎那几十分钟，所以不去也挺好。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第 1186题：删除一次得到子数组最大和，难度是中等。
给你一个整数数组，返回它的某个非空子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
示例1：
输入 ：arr = [1,-2,0,3]
输出 ：4
解释 ：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例2：
输入 ：arr = [1,-2,0,3]
输出 ：4
解释 ：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
-
1 <= arr.length <= 10^5
-
-10^4 <= arr[i] <= 10^4
问题分析
这题说的是从原数组中最多删除一个元素，然后求最大连续子数组的和，实际上这是一道动态规划的问题。
我们定义dp[i][0]表示没有删除任何元素且以arr[i]为结尾的最大连续子数组之和。
dp[i][1]表示最多删除一个元素且以
arr[i]为结尾的最大连续子数组之和，删除前以arr[i]为结尾的也算。最后保存最大值即可。
很明显我们可以得出：
dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];
dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
dp[i][0]表示没有删除任何元素，以它结尾的最大连续子数组之和是它自己arr[i]加上它前面的连续子数组之和，如果它前面的连续子数组之和为负数，就不要加了 。
dp[i][1]表示最多删除一个元素，也可能是之前就已经删除过，所以我们取
dp[i - 1][1] + arr[i]，也可能是之前没有删除过，而是把当前的元素arr[i]给删除了，我们取
dp[i - 1][0]，这两种情况我们取最大值即可。
动态规划有了递推公式就简单了，我们在看下Base Case，第一个元素如果没有删除，则 dp[0][0] = arr[0]；如果删除了，则 dp[0][1] = 0。
JAVA：
public
int
maximumSum
(
int
[] arr)
{
int
n = arr.length;
int
[][] dp =
new
int
[n][
2
];
dp[
0
][
0
] = arr[
0
];
// 第一个元素没有删除
dp[
0
][
1
] =
0
;
// 第二个元素被删除
int
ans = arr[
0
];
// 保存最大值。
for
(
int
i =
1
; i < arr.length; i++) {
dp[i][
0
] = Math.max(dp[i -
1
][
0
],
0
) + arr[i];
dp[i][
1
] = Math.max(dp[i -
1
][
1
] + arr[i], dp[i -
1
][
0
]);
ans = Math.max(ans, Math.max(dp[i][
0
], dp[i][
1
]));
}
return
ans;
}
C++：
public
:
int
maximumSum
(
vector
<
int
> &arr)
{
int
n = arr.size();
vector
<
vector
<
int
>>
dp
(n,
vector
<
int
>(
2
,
0
))
;
dp[
0
][
0
] = arr[
0
];
// 第一个元素没有删除
dp[
0
][
1
] =
0
;
// 第二个元素被删除
int
ans = arr[
0
];
// 保存最大值。
for
(
int
i =
1
; i < n; i++) {
dp[i][
0
] = max(dp[i -
1
][
0
],
0
) + arr[i];
dp[i][
1
] = max(dp[i -
1
][
1
] + arr[i], dp[i -
1
][
0
]);
ans = max(ans, max(dp[i][
0
], dp[i][
1
]));
}
return
ans;
}
最后欢迎
，你将获得：AI开发项目课程、苏三AI项目、
商城微服务实战、秒杀系统实战
、
商城系统实战、秒杀系统实战、代码生成工具、系统设计、性能优化、技术选型、底层原理、Spring源码解读、工作经验分享、痛点问题
、面试八股文
等多个优质专栏。
还有1V1答疑、修改简历、职业规划、送书活动、技术交流。
扫描下方二维码，即可加入星球：
目前星球已经更新了 5200+ 篇优质内容，还在持续爆肝中.....
星球已经被 官方推荐了3次 ，收到了小伙伴们的一致好评。戳我加入学习，已有 1600+ 小伙伴加入学习。
苏三的免费八股文网站：