2021-04-07：给定一个非负数组arr，长度为N，那么有N-1种方案可以把arr切成左右两部分
16lz
2021-04-07
2021-04-07：给定一个非负数组arr，长度为N，那么有N-1种方案可以把arr切成左右两部分，每一种方案都有，min{左部分累加和，右部分累加和}，求这么多方案中，min{左部分累加和，右部分累加和}的最大值是多少？ 整个过程要求时间复杂度O(N)。
福大大 答案2021-04-07：
自然智慧即可。
1.算出总累加和。
2.依次遍历，算出左累加和、右累加和。假设最小值是min。
3.当min大于ans时，保存min到ans中。
4.当左累加和大于右累加和时，退出循环。
5.返回ans。
代码用golang编写。代码如下：
package mainimport "fmt"func main() { arr := []int{1, 2, 3, 0, 0, 100, 1, 1} ret := bestSplit(arr) fmt.Println(ret)}func bestSplit(arr []int) int { if len(arr) < 2 { return 0 } N := len(arr) sumAll := 0 for i := 0; i < N; i++ { sumAll += arr[i] } ans := 0 sumL := 0 // [0...s] [s+1...N-1] for s := 0; s < N-1; s++ { sumL += arr[s] sumR := sumAll - sumL ans = getMax(ans, getMin(sumL, sumR)) if sumL > sumR { break } } return ans}func getMax(a int, b int) int { if a > b { return a } else { return b }}func getMin(a int, b int) int { if a < b { return a } else { return b }}执行结果如下：
左神java代码
评论
你的鼓励让我更有动力
赞赏
0人进行了赞赏支持
更多相关文章
- 程序员业余时间写的代码也算公司的？Nginx之父被捕引发争议
- 阁下可知文言编程之精妙？CMU本科生开源文言文编程语言，数天2K星
- 【免费开源】基于Vue和Quasar的crudapi前端SPA项目实战—环境搭
- MySql数据库列表数据分页查询、全文检索API零代码实现
- 【精简教程版】100行代码入手天池CV赛事
- Python信用评分卡建模（附代码）
- 一篇常做错的经典JS闭包面试题
- 工具需用好，阅读源码没烦恼
- 用 Hypothesis 来自动化单元测试