9.28 Lucid Software OA （题目+allpass答案）

9.28 Lucid OA
只有一道题，时间显示还有9天多，但邮件写的是7天内做完就好。

1题目是 Largest Su

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

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

。希望可以帮到大家！
求求好心人们给点米呀～给米不扣自己的 ：D

楼主你好，我做到了这个原题，也采用了和你一样的思路但是只过了9/14个case
我的思路是先计算二维prefixsum，然后对维度从0到n-1进行二分法，计算mid维度的当前maxsum，并最终确定满足小于等于maxSum的最大维度。但是不知道为什么有些case死活过不去，感觉时间复杂度已经降到最低了。想问一下楼主当时做的时候有没有用到一些tricky的技巧。感激不尽！

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

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

Ethan_LLL 发表于 2022-10-4 13:43
方法看起来一样的，我当时并没有遇到什么corner cases，是写完debug了一小下就全过了，但感觉会在算区域 ...

是语言问题，我用的python死活过不了两个case，然后就让朋友帮我翻译成cpp试了一下，秒过。感谢楼主，楼主有后续了吗？

虽然都是N^2log(N)的复杂度，但是python的常数复杂度太高了，换成java就过了。