店面出Longest Increasing Subsequence真的很过分吗

这题lc上不是medium吗，平方复杂度的解应该很基础吧...

如果只给出N^2的dp解法楼主会给过不，NLogN感觉不是刷过的话，没有提示很难想

taniyama007 发表于 2020/06/23 06:08:53
好奇地问一下，如果没用greedy而用DP解这题（非最优解），楼主会给过吗？

他但凡能给一个跑得过的，我都会让他过

MacJordan 发表于 2020/06/23 06:22:38
如果只给出N^2的dp解法楼主会给过不，NLogN感觉不是刷过的话，没有提示很难想

会让过的，紫薯紫薯

美国小哥哥面微软，还是出easy的variation比较好

这么说吧，这题难吗？难，涉及到DP的都不太会是简单题。不难，因为它太经典了，你甚至用背算法的方式也能过。
所以最好的解决办法就是：不要出那种实际门槛很高的原题，我之前和同事聊天聊过这个事情，他们大部分说如果不专门去看KMP，面试直接原题他们也没把握现场写出来那个算法。
这个东西就是仁者见仁，智者见智的。没法评判对错。

这写个O（N^2）简单的不能再简单了吧？难道全出two sum？

TensorFrozen 发表于 2020-6-23 05:56
美国人好日子过太久了🤣🤣

看到你这评论，我笑了。

zackwan2020 发表于 2020-6-23 05:52
当然算难了。
DP题除非很熟练，哪怕有思路也不容易做出来，尤其在面试那种环境下精神紧张，哪怕知道用DP也 ...

对，全出two sum，你去和烙印比吹牛逼吧