2021-04-17：给定一个整型数组 arr，数组中的每个值都为正数，表示完成一幅画作需要的时间，再 给定 一

2021-04-17：给定一个整型数组 arr，数组中的每个值都为正数，表示完成一幅画作需要的时间，再 给定 一个整数 num，表示画匠的数量，每个画匠只能画连在一起的画作。所有的画家 并行工作，请 返回完成所有的画作需要的最少时间。【举例】arr=[3,1,4]，num=2。最好的分配方式为第一个画匠画 3 和 1，所需时间为 4。第二个画匠画 4，所需时间 为 4。 因为并行工作，所以最少时间为 4。如果分配方式为第一个画匠画 3，所需时 间为 3。第二个画 匠画 1 和 4，所需的时间为 5。那么最少时间为 5，显然没有第一 种分配方式好。所以返回 4。arr=[1,1,1,4,3]，num=3。最好的分配方式为第一个画匠画前三个 1，所需时间为 3。第二个画匠画 4，所需时间 为 4。 第三个画匠画 3，所需时间为 3。返回 4。

福大大 答案2021-04-17：

二分法。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {
    arr := []int{2, 6, 3, 5}
    M := 2
    ret := splitArray3(arr, M)
    fmt.Println(ret)
}
func splitArray3(nums []int, M int) int {
    sum := int64(0)
    for i := 0; i < len(nums); i++ {
        sum += int64(nums[i])
    }
    l := int64(0)
    r := int64(sum)
    ans := int64(0)
    for l <= r {
        mid := int64((l + r) / 2)
        cur := getNeedParts(nums, mid)
        if cur <= M {
            ans = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return int(ans)
}
func getNeedParts(arr []int, aim int64) int {
    for i := 0; i < len(arr); i++ {
        if int64(arr[i]) > aim {
            return math.MaxInt32
        }
    }
    parts := 1
    all := arr[0]
    for i := 1; i < len(arr); i++ {
        if int64(all+arr[i]) > aim {
            parts++
            all = arr[i]
        } else {
            all += arr[i]
        }
    }
    return parts
}

执行结果如下：

左神java代码
力扣410. 分割数组的最大值