split_K_max.h

#ifndef SPLIT_K_MAX_H
#define SPLIT_K_MAX_H
 
#ifdef __cplusplus
#include <algorithm>
#include <climits>
#include <iostream>
#include <numeric>
#include <vector>
#endif
 
namespace helpers {
bool check(std::vector<int>& v, int mid, int K) {
    int sum = 0;
    int splits = 1;
 
    for (int i = 0; i < int(v.size()); i++) {
        if (v[i] > mid) {
            return false;
        }
 
        sum += v[i];
        if (sum > mid) {
            splits++;
            sum = v[i];
        }
    }
 
    return (splits <= K) ? true : false;
}
} // namespace helpers

int minimum_max_sub_sum(std::vector<int>& v, int K) {
    int start = v[0];
    int end = std::accumulate(v.begin(), v.end(), 0);
 
    int ans = INT_MAX;
    while (start <= end) {
        int mid = start + (end - start) / 2;
 
        if (helpers::check(v, mid, K)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
 
    return ans;
}
 
#endif