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 $\le k$.

1#include <bits/stdc++.h> 
2using namespace std;
3
4using ll = long long;
5
6using vi = vector<int>;
7#define pb push_back
8#define rsz resize
9#define all(x) begin(x), end(x)
10#define sz(x) (int)(x).size()