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

举报
福大大架构师每日一题 发表于 2021/04/07 21:48:11 2021/04/07
【摘要】 2021-04-07:给定一个非负数组arr,长度为N,那么有N-1种方案可以把arr切成左右两部分,每一种方案都有,min{左部分累加和,右部分累加和},求这么多方案中,min{左部分累加和,右部分累加和}的最大值是多少? 整个过程要求时间复杂度O(N)。福大大 答案2021-04-07:自然智慧即可。1.算出总累加和。2.依次遍历,算出左累加和、右累加和。假设最小值是min。3.当min...

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。