410. Split Array Largest Sum

leetcode easy

#array#bit-manipulation#csharp#easy#leetcode#search#two-pointers

Task

Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива.

Пример:

Input: nums = [7,2,5,10,8], k = 2

Output: 18

C# solution

matched/original

public class Solution {
    public int SplitArray(int[] nums, int k) {
        int left = nums.Max();
        int right = nums.Sum();
        while (left < right) {
            int mid = (left + right) / 2;
            if (CanSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private bool CanSplit(int[] nums, int k, int maxSum) {
        int currentSum = 0;
        int subarrays = 1;
        foreach (int num in nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SplitArray(vector<int>& nums, int k) {
        int left = nums.Max();
        int right = nums.Sum();
        while (left < right) {
            int mid = (left + right) / 2;
            if (CanSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private bool CanSplit(vector<int>& nums, int k, int maxSum) {
        int currentSum = 0;
        int subarrays = 1;
        foreach (int num in nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

Java solution

matched/original

public class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canSplit(int[] nums, int k, int maxSum) {
        int currentSum = 0, subarrays = 1;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

JavaScript solution

matched/original

function splitArray(nums, k) {
    function canSplit(nums, k, maxSum) {
        let currentSum = 0;
        let subarrays = 1;
        for (const num of nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
    
    let left = Math.max(...nums);
    let right = nums.reduce((a, b) => a + b, 0);
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canSplit(nums, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Python solution

matched/original

def splitArray(nums, k):
    def canSplit(nums, k, maxSum):
        currentSum = 0
        subarrays = 1
        for num in nums:
            if currentSum + num > maxSum:
                currentSum = num
                subarrays += 1
                if subarrays > k:
                    return False
            else:
                currentSum += num
        return True
    
    left, right = max(nums), sum(nums)
    while left < right:
        mid = (left + right) // 2
        if canSplit(nums, k, mid):
            right = mid
        else:
            left = mid + 1
    return left

Go solution

matched/original

package main

func splitArray(nums []int, k int) int {
    left, right := max(nums), sum(nums)
    for left < right {
        mid := (left + right) / 2
        if canSplit(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canSplit(nums []int, k int, maxSum int) bool {
    currentSum, subarrays := 0, 1
    for _, num := range nums {
        if currentSum + num > maxSum {
            currentSum = num
            subarrays++
            if subarrays > k {
                return false
            }
        } else {
            currentSum += num
        }
    }
    return true
}

func max(nums []int) int {
    maxNum := nums[0]
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }
    return maxNum
}

func sum(nums []int) int {
    total := 0
    for _, num := range nums {
        total += num
    }
    return total
}

Explanation

Algorithm

Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму.

Если возможно разбить массив для данной средней суммы, уменьшите верхнюю границу. Если нет, увеличьте нижнюю границу. Повторяйте до тех пор, пока границы не сойдутся.

😎