leetcode410. 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.

길이 가 n 인 정수 배열 을 m 개의 비 어 있 는 연속 서브 배열 로 나 누고 각 하위 배열 의 모든 요소 의 합 을 계산한다.이 분할 방식 이 생 성 되 는 최대 하위 배열 과 모든 분할 방식 에서 가장 작은 분할 방식 을 구 합 니 다.
예 를 들 어 문제 중의 예 nums = [7,2,5,10,8]，m = 2 는 모두 네 가지 분할 방식 이 있다.

[7], [2,5,10,8]

[7,2], [5,8,10]

[7,2,5], [8,10]

[7,2,5,8], [10]

그 중에서 세 번 째 분할 로 얻 은 가장 큰 하위 배열 의 합 은 모든 분할 에서 가장 작은 것 이다.
사고 1: 동적 계획
우선, 우 리 는 재 귀적 인 방식 으로 모든 분할 방식 을 옮 겨 다 니 며 모든 분할 방식 에서 요구 에 가장 부합 되 는 결 과 를 찾 을 수 있다.코드 는 다음 과 같 습 니 다:

    public int splitArray(int[] nums, int m) {
        //  [0...i]       
        int[] sums = new int[nums.length+1];
        for(int i = 1 ; i<=nums.length ; i++) {
            sums[i] = nums[i-1] + sums[i-1];
        }
        return splitArray(nums, m, 0, sums);
    }
    
    //   cur    ，     m           
    public int splitArray(int[] nums, int m, int cur, int[] sums) {
        if(m == 1) {
            return sums[nums.length] - sums[cur];
        }
        int min = Integer.MAX_VALUE;
        int diff = Integer.MAX_VALUE;
        for(int i = cur+1 ; i<=nums.length-m+1 ; i++) {
            //      ，          
            int left = sums[i]-sums[cur];
            //             splitArray  
            int right = splitArray(nums, m-1, i, sums);
            //               ，             ，       
            if(diff < Math.abs(left - right)) {
                break;
            }
            diff = Math.abs(left - right);
            min = Math.min(min, Math.max(left, right));
        }
        return min;
    }

이런 방법 은 빅 데이터 양의 장면 에서 시간 을 초과 하 는 문제 가 발생 할 수 있다. 본질은 우리 가 중간의 모든 장면 을 충분히 복용 하지 못 한 데 있다. 예 를 들 어 [i - j] 라 는 하위 그룹의 k 차 분할 에 대한 가장 좋 은 결과 이다.만약 에 우리 가 i 에서 배열 의 끝 에서 k 차 분할 을 하 는 가장 좋 은 결 과 를 기록 하면 이 결 과 는 dp[i][k] 이 고 j 에서 배열 의 끝 에서 k + 1 차 분할 을 하 는 가장 좋 은 결 과 는 min(max(num(j), dp[j+1][k]), max(nums(j)+num(j+1), dp[j+2][k])... ) 코드 는 다음 과 같다.

    public int splitArray(int[] nums, int m)
    {
        int L = nums.length;
        //  0-i    
        int[] S = new int[L+1];
        S[0]=0;
        for(int i=0; i

사고방식 2: 이분법
이것 은 매우 생각 하기 어 려 운 방법 이다.이분법 의 난점 은 초기 경 계 를 어떻게 구분 하고 경 계 를 어떻게 점차적으로 축소 하 며 좌우 지침 이 만 날 수 있 도록 확보 하 는 데 있다.여기 서 경 계 는 이 배열 에서 얻 을 수 있 는 하위 배열 요소 와 최소 값, 최대 값 으로 설정 되 어 있 습 니 다.기본 상식 에 따 르 면 배열 의 최대 요 소 는 이 배열 이 분 단 된 하위 배열 의 요소 와 하 계 를 결정 하고 배열 의 요소 와 상 계 는 배열 의 모든 요소 의 합 을 초과 하지 않 을 것 이다.배열 요소 와 상계 와 하 계 를 확정 한 후 마지막 까지 구간 을 계속 압축 하 는 방법 을 찾 아야 한다.
중간 위 치 를 배열 요소 와 경계 로 사용 할 수 있 습 니 다. 즉, 모든 연속 배열 의 합 이 mid 값 을 초과 하지 않 는 다 고 가정 할 수 있 습 니 다.만약 에 이런 방식 으로 얻 은 분할 결과 가 규정된 m 개 보다 크다 면 mid 값 은 최대 요소 와 상계 로 서 m 키 배열 만 나 눌 수 없 기 때문에 최대 요소 와 상 계 는 반드시 mid 와 경계 중간 에 있다 는 것 을 의미한다.같은 이치 로 만약 에 이런 방식 으로 얻 은 분할 결과 가 규정된 m 개 보다 작다 면 mid 값 이 최대 원소 와 상계 로 서 m 자 그룹 을 분할 하 는 것 을 만족 시 킬 수 있 지만 더 좋 은 해석 이 존재 할 수 있다 는 것 을 의미한다.이런 이분법 사고방식 을 통 해 얻 은 마지막 결 과 는 필요 한 최소 분할 결과 이다.

    public int splitArray2(int[] nums, int m) {
        long sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i target) {
                sum = nums[i];
                count++;
                if(count > m) {
                    return false;
                }
            }
        }
        return true;
    }