410. Split Array Largest Sum ---H !~~~~~~

Given an array nums 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.

 

Example 1:

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.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

 

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= m <= min(50, nums.length)

A:

首先，试图计算平均值，再每次尽量均分。

 但这样， 会有一种情况

average = 100,   m = 

1,2,4,5,6 99,99, 10, 9 ,8 , 7, .....    这样的情况，还是需要把两个99 分开。 那样左

这样结束后， 需要 左右挪动 每个位置，  这样就会互相影响。

因此，这个应该是行不通的。

-------》  考虑分而治之的思想 , 再考虑， m的情况，可以分为 a+b = m的两种情况，因此我们试着考虑DP 算法

首先我考虑的是2维的DP，就是对于index (a,b) inclusive, 可以分成的最小的情况。

但是由于 m == 14,000，因此可能空间太大了。

因此考虑1维的， 由此变成，每次取下最前面的一个（或者几个），然后再分后面的till the end of nums array。

由此，数组就变成了 n * m的了。

这个题目比普通DP 困难之处是：

每次m 增加一个，  那么之前的所有的index 从  a 到  b, 都需要重新update. 而不是规定于某一个index

状态转移方程不好写。

那么我用 HashMap 来存储。

那么，我们对于每一个从 [ a, b]  ---> minSum with  k subarray.

再想一下，其实 a 永远都是0 的，

所以，我们就可以有了DP 的方式。

每行 从k = 1...m   然后每个DP[k][end] 的值是从 [0, end] 被分为k 个subarray的minSum

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); vector<int> total = nums; // get the total sum for m == 1 (per each ending index) for(int i= 1; i<n;i++){ total[i] += total[i-1]; } vector<int> DP = total; // DP[i] stands for [0,i] the minSum of k_split subarray for(int k = 2; k<=m; k++){ vector<int> newDP(n, INT_MAX); for(int cur = k-1; cur < n; cur++){ for(int preLast = k-2; preLast<cur; preLast++){ int minSplitSum = DP[preLast]; int curLastSum = total[cur]-total[preLast]; newDP[cur] = min(newDP[cur], max( minSplitSum, curLastSum)); if(curLastSum<=minSplitSum){ // no need to shrink break; } } } DP = newDP; } return DP[n-1]; } };

这个题的改善是可以在line 15的for loop, 写成 binary search.  

Error:

Line 18,  一开始糊涂， 写成了  min(  ,  min ()  )  哎，