package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/split-array-largest-sum/
 */
public class Problem410 {
    public int splitArray(int[] nums, int m) {
        int[] sums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                sums[i] = nums[i];
            } else {
                sums[i] = sums[i - 1] + nums[i];
            }
        }
        return splitArray(nums, sums, m, 0, new ArrayList<>());
    }

    private static int splitArray(int[] nums, int[] sums, int m, int idx, List<Integer> subList) {
        if (m <= 1) {
            subList.add(sums[nums.length - 1]);
            int max = 0;
            for (int i = subList.size() - 1; i >= 0; i--) {
                if (i == 0) {
                    max = Math.max(max, subList.get(i));
                } else {
                    max = Math.max(max, subList.get(i) - subList.get(i - 1));
                }
            }
            return max;
        }
        int min = Integer.MAX_VALUE;
        for (int i = idx; i < nums.length; i++) {
            List<Integer> newSubList = new ArrayList<>(subList);
            newSubList.add(sums[i]);
            min = Math.min(min, splitArray(nums, sums, m - 1, i + 1, newSubList));
        }
        return min;
    }

    public static void main(String[] args) {
        Problem410 prob = new Problem410();
        System.out.println(prob.splitArray(new int[]{7, 2, 5, 10, 8}, 2)); // 18
        System.out.println(prob.splitArray(new int[]{7, 2, 5, 10, 8}, 3)); // 14
        System.out.println(prob.splitArray(new int[]{7, 2, 5, 10, 8}, 4)); // 10
        System.out.println(prob.splitArray(new int[]{7, 2, 5, 10, 8}, 5)); // 10
    }
}

@@ -16,60 +16,8 @@
 e;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 /**%0A
@@ -389,32 +389,73 @@
     %7D%0A        %7D%0A
+        int%5B%5D sumSubArrays = new int%5Bm%5D;%0A
         return s
@@ -486,25 +486,23 @@
  0, 
-new ArrayList%3C%3E()
+0, sumSubArrays
 );%0A 
@@ -584,30 +584,81 @@
 idx,
- List%3CInteger%3E subList
+%0A                                  int sumSubArrayIdx, int%5B%5D sumSubArrays
 ) %7B%0A
@@ -693,26 +693,45 @@
       su
-bList.add(
+mSubArrays%5BsumSubArrayIdx%5D = 
 sums%5Bnum
@@ -743,17 +743,16 @@
 gth - 1%5D
-)
 ;%0A      
@@ -801,20 +801,25 @@
 = su
-bList.size()
+mSubArrays.length
  - 1
@@ -907,28 +907,29 @@
 (max, su
-bList.get(i)
+mSubArrays%5Bi%5D
 );%0A     
@@ -994,41 +994,43 @@
 , su
-bList.get(i) - subList.get(
+mSubArrays%5Bi%5D - sumSubArrays%5B
 i - 1
-)
+%5D
 );%0A 
@@ -1197,96 +1197,46 @@
     
-List%3CInteger%3E newSubList = new ArrayList%3C%3E(subList);%0A            newSubList.add(
+sumSubArrays%5BsumSubArrayIdx%5D = 
 sums%5Bi%5D
-)
 ;%0A  
@@ -1305,19 +1305,57 @@
 + 1,
- newSubList
+%0A                sumSubArrayIdx + 1, sumSubArrays
 ));%0A
@@ -1800,20 +1800,117 @@
  5)); // 10%0A
+        System.out.println(prob.splitArray(new int%5B%5D%7B1, 2, 4, 5, 6, 10, 2, 4, 10, 4%7D, 8)); // 10%0A
     %7D%0A%7D%0A

Update problem 410