CSES - Array Division

In this problem, we're asked to divide an array into $k$ subarrays such that the maximum sum of a subarray is minimized.

Binary Search

Let's begin by making an important observation. First of all, if you can divide an array such that the maximum sum is at most $x$, you can also divide the array such that the maximum sum is at most $y > x$ with the same division.

Greedy

Now, given some maximum sum $x$, we can check whether a division is possible using a greedy algorithm. If we can divide the array into $s < k$ subarrays, then we can divide it into $k$ subarrays without increasing the maximum sum of a subarray. Therefore, we can greedily create subarrays as long as the sum of the subarray does not exceed $x$, and check if the number of subarrays is $\leq k$.

#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()