LeetCode 410. Split Array Largest Sum

原题链接在这里:<https://leetcode.com/problems/split-array-largest-sum/&gt;

题目:

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
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.

题解:

Let dp[i][j] denotes up to index j, with i cut, the minimum of largest sum of subarrays.

Thus with i = 0, that means there is no cut. Initialize dp[0][j] as sum of nums[0] to nums[j].

For dp[i][j], we could cut at (0, 1, .... j -1). And minimize Math.max(dp[i - 1][k], dp[0][j] - dp[0][k]).

Time Complexity: O(m * n ^ 2). n = nums.length.

Space: O(m * n).

AC Java:

 1 class Solution {
 2     public int splitArray(int[] nums, int m) {
 3         if(nums == null || nums.length == 0){
 4             return 0;
 5         }
 6         
 7         int n = nums.length;
 8         int [][] dp = new int[m][n];
 9         dp[0][0] = nums[0];
10         for(int j = 1; j &lt; n; j++){
11             dp[0][j] = dp[0][j - 1] + nums[j]; 
12         }
13         
14         for(int i = 1; i &lt; m; i++){
15             for(int j = i; j &lt; n; j++){
16                 int min = Integer.MAX_VALUE;
17                 for(int k = 0; k &lt; j; k ++){
18                     min = Math.min(min, Math.max(dp[i - 1][k], dp[0][j] - dp[0][k]));
19                 }
20                 
21                 dp[i][j] = min;
22             }
23         }
24         
25         return dp[m - 1][n - 1];
26     }
27 }

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。