410. Split Array Largest Sum

Hard

8.2K

175

Given an integer array `nums`

and an integer `k`

, split `nums`

into `k`

non-empty subarrays such that the largest sum of any subarray is **minimized**.

Return *the minimized largest sum of the split*.

A **subarray** is a contiguous part of the array.

**Example 1:**

Input:nums = [7,2,5,10,8], k = 2Output:18Explanation:There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

**Example 2:**

Input:nums = [1,2,3,4,5], k = 2Output:9Explanation:There are four ways to split nums into two subarrays. The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

**Constraints:**

`1 <= nums.length <= 1000`

`0 <= nums[i] <= 10`

^{6}`1 <= k <= min(50, nums.length)`

Accepted

266.4K

Submissions

496.7K

Acceptance Rate

53.6%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved