split_array_largest_sum.cc

// https://leetcode.com/problems/split-array-largest-sum

// Same as https://www.codingninjas.com/codestudio/library/book-allocation-problem

class Solution {
public:
    /*
     * Let dp[i][j + 1] be the an optimal solution to the subproblem with i subarrays within
     * A[0..j]. Let sum[i][j] be the sum of the numbers in A[i..j]. Then:
     *
     * dp[1][j + 1] = sum[0][j].
     *
     * dp[i][j + 1] = min_{i - 1 <= k <= j} max(dp[i - 1][k], sum[k][j]).
     *
     * As we only need to store the previous value dp[i - 1][k], we can simply use a 1D array:
     *
     * - Initialisation: for each j, dp[j + 1] = sum[0][j].
     *
     * - Recursion: dp[j + 1] = min_{i - 1 <= k <= j} max(dp[k], sum[k][j])
     */
    int splitArrayDP(vector<int>& A, int m) {
        int n = A.size(), i, j;
        vector<int> dp(n + 1, INT_MAX);

        // initialization (m = 1, prefix sum)
        dp[0] = 0;
        for (i = 0; i < n; i++) dp[i + 1] = dp[i] + A[i];

        for (i = 2; i <= m; i++) // bottom-up DP (m >= 2)
            for (j = n - 1; j >= 0; j--)
                for (int k = j, sum = 0; k >= i - 1; k--) {
                    sum += A[k];
                    dp[j + 1] = min(dp[j + 1], max(dp[k], sum));
                    if (sum >= dp[k]) break; // going left won't get smaller sums
                }

        return dp[n];
    }

    /*
     * The answer is between the maximum element and the sum of all elements.
     *
     * Let X be a subarray sum. The greater X is, the more likely we can split A into m parts
     * such that X is optimal. There exists a threshold x such that if X < x, then A can only
     * be split in to more than m parts.
     *
     * We can use binary search to minimize X.
     *
     * Source: https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java
     *
     * Time: O(N * log(S)), where N is the size of the array, and S is the sum of its
     * elements.
     */
    int splitArray(vector<int>& A, int m) {
        long sum = accumulate(begin(A), end(A), 0L);

        if (m == 1) return sum;

        long left = *max_element(begin(A), end(A)), right = sum, n = A.size();

        auto valid = [&](int maxSum) {
            int count = 1, i = 0;

            for (int sum = 0; i < n && count <= m; i++) {
                sum += A[i];

                if (sum > maxSum) {
                    sum = A[i];
                    count++;
                }
            }

            return i == n && count <= m;
        };

        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (valid(mid)) right = mid - 1;
            else left = mid + 1;
        }

        return left;
    }
};