讨论/题目交流/🐱 力扣第 11 场夜喵双周赛/
🐱 力扣第 11 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛
image.png

展开讨论
力扣 (LeetCode)发起于 2019-10-19
最近编辑于 2019-11-16

关于第四题的二分解法,数组的分段最大最小和问题和最小最大和问题的思路是一样的,就是将分成K段理解为放进K个桶,使每个桶中元素之和不大于(不小于)目标值S,这个S就是我们二分的对象。S最小值为最小元素,最大值为所有元素之和。每次对S的尝试都是遍历一次数组,所以最终时间复杂度为Nlog2Smax。
这题dp也可以做,但是会超时。

5
展开全部 4 讨论