• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2021-04-07:给定一个非负数组arr,长度为N,那么有N-1种方案可以把arr切成左右两部分,每一种方案都有,min{左部分累加和,右部分累加和},求这么多方案中,min{左部分累加和,右部分

互联网 diligentman 2周前 (04-07) 4次浏览

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
    }
}

执行结果如下:
2021-04-07:给定一个非负数组arr,长度为N,那么有N-1种方案可以把arr切成左右两部分,每一种方案都有,min{左部分累加和,右部分累加和},求这么多方案中,min{左部分累加和,右部分


左神java代码
评论

展开阅读全文

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

2021-01-06:mysql中,我存十亿个手机号码,考虑存储空间和查询效率,用什么类型的字段去存?
2020-12-12:现场写代码,把CPU打满,java和go都行,并解释为什么。
2021-01-19:mysql中,一张表里有3亿数据,未分表,其中一个字段是企业类型,企业类型是一般企业和个体户,个体户的数据量差不多占50%,根据条件把个体户的行都删掉。请问如何操作?
2021-03-05:go中,io密集型的应用,比如有很多文件io,磁盘io,网络io,调大GOMAXPROCS,会不会对性能有帮助?为什么?


喜欢 (0)