AllocateBooks-v1.java

/*
Binary search and Greedy 
*/

public int allocatebooksII(int n, int B, int[] A) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            sum += A[i];
            max = Math.max(max, A[i]);
        }
        // binary search by range
        int l = max;
        int r = sum;

        while(l < r) {
            int mid = l + (r - l) / 2;
            if (isValid(A, B, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public boolean isValid(int[] A, int B, int val) {
        int cnt = 0;
        int sub = 0;

        for (int num : A) {
            if (sub + num > val) {
                sub = num;
                cnt += 1;
                if (cnt >= B) {
                    return false;
                }
            } else {
                sub += num;
            }
        }
        return true;
    }

AllocateBooks-v2.java

/*
Naive DP
*/
public int allocatebooksI(int n, int B, int[] A) {
        long[][] dp = new long[n + 1][B + 1];
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + A[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }

        for (int j = 1; j <= B; j++) {
            for (int i = j; i <= n; i++) {
                long sum_i = sum[i] - sum[0];
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < i; k++) {
                    long sum_k = sum[k] - sum[0];
                    long curr_sub = sum_i - sum_k;
                    dp[i][j] = Math.min(dp[i][j], Math.max(curr_sub, dp[k][j - 1]));
                }
            }
        }
        return (int)dp[n][B];
    }

AllocateBooks.java

import org.junit.Test;

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;

public class AllocateBooks {
    //https://leetcode.com/problems/split-array-largest-sum/
    class InputValues {
        int n;
        int B;
        int[] A;
        public InputValues(int n, int B, int[] A) {
            this.n = n;
            this.B = B;
            this.A = A;
        }
        @Override
        public String toString() {
            return "n: " + n + "\n" + "B: " + B + "\n" + "A length: " + A.length;
        }
    }

    @Test
    public void test() {
        File[] files = readFolder("src/input/AllocateBooks");
        for (File file : files) {
            AllocateBooks.InputValues testcase = readFile(file);
            int res1 = allocatebooksI(testcase.n, testcase.B, testcase.A);
            int res2 = allocatebooksII(testcase.n, testcase.B, testcase.A);
            System.out.println("test: " + file.getName());
            System.out.println("res dp: " + res1 + "\tres bs: " + res2);
            assert res1 == res2;
        }
    }

    public void generateOutput() throws IOException {
        File[] files = readFolder("src/input/AllocateBooks");
            for (File file : files) {
                AllocateBooks.InputValues testcase = readFile(file);
                int res2 = allocatebooksII(testcase.n, testcase.B, testcase.A);
                String outfileName = "src/output/AllocateBooks/" + file.getName().replace(".in", ".out");
                File outfile = new File(outfileName);
                outfile.getParentFile().mkdirs();
                outfile.createNewFile();
                PrintWriter printWriter = new PrintWriter(new FileWriter(outfileName));
                printWriter.println(res2);
                printWriter.close();
            }
    }

    public int allocatebooksI(int n, int B, int[] A) {
        long[][] dp = new long[n + 1][B + 1];
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + A[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }

        for (int j = 1; j <= B; j++) {
            for (int i = j; i <= n; i++) {
                long sum_i = sum[i] - sum[0];
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < i; k++) {
                    long sum_k = sum[k] - sum[0];
                    long curr_sub = sum_i - sum_k;
                    dp[i][j] = Math.min(dp[i][j], Math.max(curr_sub, dp[k][j - 1]));
                }
            }
        }
        return (int)dp[n][B];
    }


    public int allocatebooksII(int n, int B, int[] A) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            sum += A[i];
            max = Math.max(max, A[i]);
        }
        // binary search by range
        int l = max;
        int r = sum;

        while(l < r) {
            int mid = l + (r - l) / 2;
            if (isValid(A, B, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public boolean isValid(int[] A, int B, int val) {
        int cnt = 0;
        int sub = 0;

        for (int num : A) {
            if (sub + num > val) {
                sub = num;
                cnt += 1;
                if (cnt >= B) {
                    return false;
                }
            } else {
                sub += num;
            }
        }
        return true;
    }

    
    private int getInt(String name) {
        return Integer.parseInt(name.replaceAll("\\D", ""));
    }

    private File[] readFolder(String path) {
        File folder = new File(path);
        File[] files = folder.listFiles();
        Arrays.sort(files, (a, b) -> getInt(a.getName()) - getInt(b.getName()));
        return files;
    }

    private InputValues readFile(File file) {
        try {
            // assume the input file is always valid
            Scanner sc = new Scanner(file);
            int n = Integer.parseInt(sc.next());
            int B = Integer.parseInt(sc.next());
            sc.nextLine(); // skip current line
            String[] line2 = sc.nextLine().split(" ");
            int[] A = new int[line2.length];
            for (int i = 0; i < line2.length; i++) {
                A[i] = Integer.parseInt(line2[i]);
            }
            sc.close();
            return new InputValues(n, B, A);
        } catch (FileNotFoundException e) {
            System.out.println(file.getName() + " not exist");
        }
        return null;
    }
}