2021-04-07:给定一个非负数组arr,长度为N,那么有N-1种方案可以把arr切成左右两部分

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代码
评论

©著作权归作者所有:来自51CTO博客作者福大大的原创作品,如需转载,请注明出处,否则将追究法律责任

你的鼓励让我更有动力

赞赏

0人进行了赞赏支持