骨骼新鲜电面

uestchx1 发表于 2018-12-5 10:37
这道题的discuss里面挺详细的，有扩展到n个subarray，长度均为k的情况
https://leetcode.com/problems/max ...

我仔细看看，非常感谢！

第一题是不是直接找出nums里面最大的两个数就行了（不是同一个index, value可能相同）？O（n）?

soliloquyyy 发表于 2018-12-5 12:54
第一题是不是直接找出nums里面最大的两个数就行了（不是同一个index, value可能相同）？O（n）?

长度是k的subarray，不能只找最大的两个吧，不过复杂度还是o(n)

soliloquyyy 发表于 2018-12-5 12:54
第一题是不是直接找出nums里面最大的两个数就行了（不是同一个index, value可能相同）？O（n）?

sorry,没看到连续的，如果是这样的，sliding windows确实可以。

我很爱学习 发表于 2018-12-5 12:56
长度是k的subarray，不能只找最大的两个吧，不过复杂度还是o(n)

唉，看题不仔细，没看到K也没看到连续的。
抱歉

第二题类似利口留疤就

风屏 发表于 2018-12-6 15:43
第二题类似利口留疤就

嗯嗯看了下是的

如果只是两个的话，感觉用两个sum就好了

CCkeHooo 发表于 2018-12-7 05:21
如果只是两个的话，感觉用两个sum就好了

空间 o(1) 吗，不太懂。。

我很爱学习 发表于 2018-12-7 08:59
空间 o(1) 吗，不太懂。。

用两个数组， 然后分别从前往后遍历和从后往前遍历， A[i] 记录i之后的subarray最大值， B[i]记录从0到i的 subarray最大值。 所以最后只要再遍历一边数组，A[i]+B[i]最大就可以了。