拼多多笔试
拼多多笔试第二题一直0%,有没有大佬第二题过了的说一下思路呀


全部评论
最大子数组和为mx,数组总和为sum,那么最后结果就是mx*2^k+sum-mx,使用长整型+快速幂
当时想的是求最大子数组和(子数组可以为空)arrMax。如果arrMax是正数,那么把arrMax放到之前和最大的部分一定是最优解,所以答案就是arrSum + arrMax*(2^k-1);如果arrMax是负数,每次选0加入则是最优解,答案是arrSum。
但是想不通为什么只有 80%……
dp表示也卡80了
第二题应该是dp求最大子数组和,然后加就好了,可惜我交了才想起来dp求最大子数组和
我直接暴力求子序列的最大和,然后求序列所有元素的和,每次加最大和之后最大和*2,加k次,过了60,剩下超时了
md没用快速幂,加了k次,就过了20
请问第一题咋做的呀,暴力只能过50%
相关推荐
05-29 09:02
门头沟学院 Java 点赞 评论 收藏
分享