大家好,欢迎来到IT知识分享网。
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 main
import "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代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class41/Code01_BestSplitForAll.java)
[评论](https://user.qzone.qq.com/3182319461/blog/1617750488)
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/63182.html