leetcode 410. Maximum value of split array - (Day30)

410. The maximum value of the split array

Given an array of nonnegative integers nums And an integer m , You need to divide this array into m Non empty continuous subarray .

Design an algorithm to make this m The maximum value of sum of subarrays is the minimum .

Example 1：

Input ：nums = [7,2,5,10,8], m = 2
Output ：18
explain ： There are four ways to nums Is divided into 2 Subarray .
The best way is to divide it into [7,2,5] and [10,8] . Because the maximum value of the sum of the two subarrays is 18, Minimum in all cases .

Example 2：

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

Example 3：

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

Tips ：

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

analysis ：

• Turn the problem into ： The effect of adding an element to all the previous numbers on the result . for example ： Enumerate to 7 2 5 8 10 Medium 8 when , Translate into in 7 2 5 Add a... Based on 8 Will have an impact on the results .
• With 8 A subarray ending with may be 8 ,8 5,8 5 2,8 5 2 7, If m=3, How can I allocate , Enumerate now 8 The last four subarrays are used as the 1 Group , Let the rest of the numbers produce the rest 2 Group .
• 8 Combine oneself as a group , So you need 7 2 5 Two sets of .
• 8 5 As a group , need 7 2 Two sets of
• 8 5 2 As a group ,7 It is impossible to generate two groups, so the enumeration ends .
• Next, join 10 This element ,m=3
  With 10 The resulting subarray is ：10 ,10 8 ,10 8 5,10 8 5 2,10 8 5 2 7
  -10 As a group , be 7 2 5 8 Composition required 2 Group
  -10 8 As a group , be 7 2 5 Composition required 2 Group （ Add sub questions 8 The time has come ）
  -10 8 5 As a group , be 7 2 form 2 Group （ add to 8 It also appeared when ）
  -10 8 5 2 As a group , be 7 form 2 Group （ It is impossible to end enumeration )

We use it f[i][j] Express , By the end of i A number is generated when it ends j Group time , this j The maximum and minimum values of the respective sums of the subarrays are f[i][j].

code

class Solution {
    
public:
    //  Each element acts as the m The maximum and minimum values of the last element of a subsequence 
    int splitArray(vector<int>& nums, int m) {
    
        int n=nums.size();
        // f[0][i],f[i][0] Don't use , To prevent cross-border ,
        // Direct use f[i][j] Says to the first i End of element , It is divided into j Group time , The maximum value and the minimum value of each group 
        int f[n+1][m+1];
        memset(f,0,sizeof(f));
        //  There is only one set of cases 
        for(int i=1;i<n+1;i++){
    
            f[i][1]=nums[i-1]+f[i-1][1];
        }
        //  Enumerate each element 
        for(int i=1;i<=n;i++){
    
        	//  Enumerates the number of groups generated at the end of the current element 
            for(int j=2;j<=m;j++){
    
            	//  At present i End of element , produce j The maximum value of each group is the minimum 
                int tmp=0,tmp2=INT_MAX;
                //  Elements i The ending can be combined with at most i Elements 
                    for(int k=i;k>0;k-- ){
    
                    tmp+=nums[k-1];
                    //  If the number of groups required > Number of remaining digits 
                    if(j-1>k-1) break;
                    //  front k-1 Elements , produce j-1 The largest element of a group ,
                    // And the maximum value of the last group 
                    int a=max(tmp,f[k-1][j-1]);
                    //  Enumerate all and i Combination of elements , Minimum value 
                    tmp2=min(tmp2,a);
                }
                f[i][j]=tmp2;
            }
        }
        return f[n][m];
    }
};