Split Array Largest Sum

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        long long lo = *max_element(nums.begin(), nums.end());
        long long hi = accumulate(nums.begin(), nums.end(), 0LL);
        auto canDo = [&](long long cap) {
            int parts = 1; long long cur = 0;
            for (int x : nums) {
                if (cur + x > cap) { ++parts; cur = x; }
                else cur += x;
            }
            return parts <= k;
        };
        while (lo < hi) {
            long long mid = lo + (hi - lo) / 2;
            if (canDo(mid)) hi = mid;
            else lo = mid + 1;
        }
        return (int)lo;
    }
};

func splitArray(nums []int, k int) int {
    var lo, hi int64
    for _, x := range nums {
        if int64(x) > lo {
            lo = int64(x)
        }
        hi += int64(x)
    }
    canDo := func(cap int64) bool {
        parts, cur := 1, int64(0)
        for _, x := range nums {
            if cur+int64(x) > cap {
                parts++
                cur = int64(x)
            } else {
                cur += int64(x)
            }
        }
        return parts <= k
    }
    for lo < hi {
        mid := lo + (hi-lo)/2
        if canDo(mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return int(lo)
}

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        lo, hi = max(nums), sum(nums)

        def can_do(cap: int) -> bool:
            parts, cur = 1, 0
            for x in nums:
                if cur + x > cap:
                    parts += 1
                    cur = x
                else:
                    cur += x
            return parts <= k

        while lo < hi:
            mid = lo + (hi - lo) // 2
            if can_do(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

function splitArray(nums, k) {
    let lo = -Infinity, hi = 0;
    for (const x of nums) {
        if (x > lo) lo = x;
        hi += x;
    }
    const canDo = (cap) => {
        let parts = 1, cur = 0;
        for (const x of nums) {
            if (cur + x > cap) {
                parts++;
                cur = x;
            } else {
                cur += x;
            }
        }
        return parts <= k;
    };
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

class Solution {
    private boolean canDo(int[] nums, long cap, int k) {
        int parts = 1;
        long cur = 0;
        for (int x : nums) {
            if (cur + x > cap) {
                parts++;
                cur = x;
            } else {
                cur += x;
            }
        }
        return parts <= k;
    }

    public int splitArray(int[] nums, int k) {
        long lo = 0, hi = 0;
        for (int x : nums) {
            if (x > lo) lo = x;
            hi += x;
        }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (canDo(nums, mid, k)) hi = mid;
            else lo = mid + 1;
        }
        return (int) lo;
    }
}

function splitArray(nums: number[], k: number): number {
    let lo = -Infinity, hi = 0;
    for (const x of nums) {
        if (x > lo) lo = x;
        hi += x;
    }
    const canDo = (cap: number): boolean => {
        let parts = 1, cur = 0;
        for (const x of nums) {
            if (cur + x > cap) {
                parts++;
                cur = x;
            } else {
                cur += x;
            }
        }
        return parts <= k;
    };
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}