字节 飞书后端三面的一道面试题
-
先说我的结果： 凉了。
-
如何凉了： 就栽在这个题上了。
-
原因分析：自己还是没达到一定水平吧，题目稍微变化一下就不想想了，思维上的懒惰。
题目描述：
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
相信大家已经把剑指刷的滚瓜烂熟了。题解不用贴过来了。
面试官改了一下题目，加了一个条件：我可以有一次跳过某个数的权利，问最大和是多少？
比方说：
-2 1 -3 8
答案就变成了 9 因为我把 -3 选择跳过了。
事后诸葛亮：
class Solution {
public:
vector<int> f;
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if (!n) return 0;
vector<int> f(n + 1, 0);
vector<int> d(n + 1, 0);
int ans = nums[0];
for (int i = 1; i <= n; i++)
{
int x = nums[i - 1];
// f[i] 表示截止当前没有使用过跳过的权利的最大和
f[i] = max(x, f[i - 1] + x);
// dp[i] 记录截止当前使用了跳过的权利的最大和
d[i] = max(f[i - 1], d[i - 1] + x);
ans = max(f[i], ans);
ans = max(d[i], ans);
}
return ans;
}
};
如果我的解法不正确还请各位指正。
评论 (48)
