Split Array Largest Sum
HardExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're planning a road trip along a route broken into fixed legs, each with a known distance. The legs must be driven in order, and you need to divide them into m contiguous driving days without skipping or reordering any leg.
Each day's total distance is the sum of the legs driven that day. Return the minimum possible value for the longest single day's total distance, over every way of splitting the legs into m days.
Input: nums = [7, 2, 5, 10, 8], m = 2
Output: 18
Split the legs into [7, 2, 5] (14 total) and [10, 8] (18 total). No other split into 2 days gives a smaller longest day.
Input: nums = [1, 2, 3, 4, 5], m = 2
Output: 9
Split the legs into [1, 2, 3] (6 total) and [4, 5] (9 total). This keeps the longest day as small as possible.
Input: nums = [10], m = 1
Output: 10
With only one day available, that day must cover every leg.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.