leetcode

// 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
}