Hints — p85 Split Array Largest Sum

  1. Reframe: instead of searching over partitions, search over the answer itself — the max part-sum S.

  2. Predicate feasible(S) = “can we split into ≤ k contiguous parts, each with sum ≤ S?” This is monotone in S: feasible at S ⟹ feasible at S+1.

  3. Binary-search S in [max(nums), sum(nums)]. Lower bound max(nums) because any single part containing the max needs ≥ max.

  4. Greedy feasibility check (O(n)): accumulate left-to-right; when adding the next element would exceed S, start a new part. Count parts; feasible iff ≤ k.

  5. DP alternative: dp[i][j] = min over t of max(dp[t][j-1], prefix[i]-prefix[t]). O(n²·k). Use prefix sums.

If stuck: see solution.py.