aboutsummaryrefslogtreecommitdiff
path: root/split_array_largest_sum.c
blob: 09c03311caf5d9d7f1058a53bf2660d908742d76 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 410. Split Array Largest Sum
#include "leetcode.h"

/*
 * given an integer array 'nums' and an integer 'k' split 'nums' into 'k' non
 * empty subarrays such that the largest sum of any subarray is minimised.
 * return the minimised largest sum of the split. a subarray is a contiguous
 * part of the array
 */

int splitArray(int *nums, int numsSize, int k) {
  int right = 0, left = 0;
  for (int i = 0; i < numsSize; i++) {
    left = left > nums[i] ? left : nums[i];
    right += nums[i];
  }
  right++;
  while (left < right) {
    int mid = (left + right) / 2, cnt = 1, tmp = 0;
    for (int i = 0; i < numsSize; i++)
      if (tmp + nums[i] > mid) {
        cnt++;
        tmp = nums[i];
      } else {
        tmp += nums[i];
      }
    if (cnt > k)
      left = mid + 1;
    else
      right = mid;
  }
  return (int)left;
}

int main() {
  int n1[] = {7, 2, 5, 10, 8}, n2[] = {1, 2, 3, 4, 5};
  printf("%d\n", splitArray(n1, ARRAY_SIZE(n1), 2)); // expect: 18
  printf("%d\n", splitArray(n2, ARRAY_SIZE(n2), 2)); // expect: 9
}