骨骼新鲜电面

中午刚面完，投的是general software
开始介绍了一下是在Boston做youtube方面的，然后让我自我介绍了一下就开始写题。

您好！
本帖隐藏的内容需要积分高于 101 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 101 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

两题都做得不是很好，感觉是凉了，发出来供各位看看，另求大米，感谢！

这道题的discuss里面挺详细的，有扩展到n个subarray，长度均为k的情况
https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108230/Clean-Java-DP-O(n)-Solution.-Easy-extend-to-Sum-of-K-Non-Overlapping-SubArrays.

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

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

uestchx1 发表于 2018-12-5 10:29
第二题感觉像利口留吧酒，这里k变成了2

k还是那个k，就是subarray的长度，蠡口是找3个subarray，这里是2个，那我估计如果把2的做出来了还会follow up 3个subarray的case

感觉用presum数组是不是好一点，重复累加的运算太多了

第二题没看懂 这和直接算一个长度为2k的subarray有区别么

mysteryjoe 发表于 2018-12-5 07:38
感觉用presum数组是不是好一点，重复累加的运算太多了

第二题不知道能不能优化到o(n)

good-luck 发表于 2018-12-5 07:38
第二题没看懂 这和直接算一个长度为2k的subarray有区别么

你这样的话等于两个subarray是连在一起的，那就忽略不在一起的情况了

第二题搜在geek搜 non-overlapping subarray sum

第二题感觉像利口留吧酒，这里k变成了2

LebronRice 发表于 2018-12-5 09:41
第二题搜在geek搜 non-overlapping subarray sum

感谢！zszs