akuna oa（quant& trading python)

刚做完 感觉时间复杂度卡的很死
题目po出来了 有大佬讲解一下第二题应该怎么做吗 我只能做出

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

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

m改进了一下
求大佬解答
求米谢谢！

第二题：

1. def array_challenge(n, a):
   
2.     res = [0]
   
3.     sm = a[0]
   
4.     for i in range(1, n):
   
5.         res.append(a[i] * i - sm)
   
6.         sm += a[i]
   
7.     return res

复制代码

第二题，假设当前元素是num[i]，之前的一个元素是num[j]。那么当num[j]<num[i]时，counter加num[i]-num[j]；当num[j]>num[i]时，counter减num[j]-num[i]，即counter加num[i]-num[j]。所以两者都是num[i]-num[j]。因此只需要维持一个从0到i-1的prefix sum即可。

第三题用dp，一个存跳过当前电影的max，另一个存不跳过当前电影的max。跳过当前的应该等于不跳过前一个；不跳过当前的等于不跳过前一个加当前分数，或者跳过前一个加当前分数，两者取最大。最后两个dp[-1]取最大。
貌似存一个dp array也够了？

匿名用户 发表于 2024-09-01 21:53:34
第三题用dp，一个存跳过当前电影的max，另一个存不跳过当前电影的max。跳过当前的应该等于不跳过前一个；不跳过当前的等于不跳过前一个加当前分数，或者跳过前一个

我就这么做的 然后就testcase14 没过其他都过了 很迷

匿名用户 发表于 2024-9-2 07:50
我就这么做的 然后就testcase14 没过其他都过了 很迷

testcase 14好像是长度只有1

请问第一题咋解的，我有4个case超时了

sherrylou 发表于 2024-9-5 15:59
testcase 14好像是长度只有1

原来是这样

匿名用户 发表于 2024-9-11 23:23
请问第一题咋解的，我有4个case超时了

先sort然后用两个pointer