[Leetcode] Split Array Largest Sum

Hard : Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

Examples:

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

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

코드구현

class Solution {

    public static int count(int mid, int[] nums){
        int count = 1;
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(sum+nums[i]<=mid){
                sum+=nums[i];
            }else{
                sum = nums[i];
                count++;
            }
        }
        return count;

    }

    public int splitArray(int[] nums, int m) {
        int left = 0;
        int right = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>left) left = nums[i];
            right += nums[i];

        }



        while(left < right){
            int mid = left + (right-left)/2;
            if(count(mid, nums)<=m){
                right = mid;
            }else{
                left = mid +1;
            }
        }

        return left;
    }
}

요약

• Binary Search Tree를 이용하여 문제를 푼다.
• 왼쪽 영역으로 나눌 때 왼쪽은 max값으로 오른쪽은 sum으로 초기화하여 시작
• 중간값 = left(최소) + (right(최대)- left(최소))/2
• Point : 1) 알고리즘 선택 2) m=2인 경우로 접근하여 풀자( 3이상으로 생각하면 너무 어렵다.)