package leetcode;

/**
 * https://leetcode.com/problems/split-array-largest-sum/
 */
public class Problem410 {
    public int splitArray(int[] nums, int m) {
        // TODO
        return 0;
    }

    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
    }
}

@@ -12,16 +12,68 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 /**%0A * h
@@ -215,32 +215,1127 @@
     
-// TODO%0A        return 0
+int%5B%5D sums = new int%5Bnums.length%5D;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            if (i == 0) %7B%0A                sums%5Bi%5D = nums%5Bi%5D;%0A            %7D else %7B%0A                sums%5Bi%5D = sums%5Bi - 1%5D + nums%5Bi%5D;%0A            %7D%0A        %7D%0A        return splitArray(nums, sums, m, 0, new ArrayList%3C%3E());%0A    %7D%0A%0A    private static int splitArray(int%5B%5D nums, int%5B%5D sums, int m, int idx, List%3CInteger%3E subList) %7B%0A        if (m %3C= 1) %7B%0A            subList.add(sums%5Bnums.length - 1%5D);%0A            int max = 0;%0A            for (int i = subList.size() - 1; i %3E= 0; i--) %7B%0A                if (i == 0) %7B%0A                    max = Math.max(max, subList.get(i));%0A                %7D else %7B%0A                    max = Math.max(max, subList.get(i) - subList.get(i - 1));%0A                %7D%0A            %7D%0A            return max;%0A        %7D%0A        int min = Integer.MAX_VALUE;%0A        for (int i = idx; i %3C nums.length; i++) %7B%0A            List%3CInteger%3E newSubList = new ArrayList%3C%3E(subList);%0A            newSubList.add(sums%5Bi%5D);%0A            min = Math.min(min, splitArray(nums, sums, m - 1, i + 1, newSubList));%0A        %7D%0A        return min
 ;%0A  
@@ -1590,16 +1590,178 @@
 ; // 14%0A
+        System.out.println(prob.splitArray(new int%5B%5D%7B7, 2, 5, 10, 8%7D, 4)); // 10%0A        System.out.println(prob.splitArray(new int%5B%5D%7B7, 2, 5, 10, 8%7D, 5)); // 10%0A
     %7D%0A%7D%0A

Update problem 410