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 = 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. Note: this is the most straightforward solution, but it didn't pass the large input test case due to time out.

1 public class Solution { 2     public int SplitArray(int[] nums, int m) { 3         var sum = new int[nums.Length]; 4          5         for (int i = 0; i < nums.Length; i++) 6         { 7             sum[i] = nums[i] + (i == 0 ? 0 : sum[i - 1]);  8         } 9         10         if (m == 1) return sum[sum.Length - 1];11         12         var results = new List
     
      
       >();13         generateCombinations(nums.Length, m, 0, 0, new List
       
        (), results);14         15         var result = 0;16         var curMax = Int32.MaxValue;17         foreach (var l in results)18         {19             var last = 0;20             foreach (var i in l)21             {22                 var s = sum[i] - last;23                 last = sum[i];24                 result = Math.Max(result, s);25                 if (s >= curMax) break;26             }27             28             curMax = Math.Min(result, curMax);29             result = 0;30         }31         32         return curMax;33     }34     35     private void generateCombinations(int n, int m, int start, int cuts, IList
        
          result, IList
         
          
           > results)36 {37 if (start >= n || cuts >= m)38 {39 if (start >= n && cuts >= m)40 {41 results.Add(new List
           
            (result));42 }43 44 return;45 }46 47 for (int i = start; i < n; i++)48 {49 result.Add(i);50 generateCombinations(n, m, i + 1, cuts + 1, result, results);51 result.RemoveAt(result.Count - 1);52 }53 }54 }