// DP 1

public int splitArray(int[] nums, int m) {

int n = nums.length;

int[] sum = new int[n+1];

for (int j=1; j<=n; j++) sum[j] += sum[j-1] + nums[j-1];

int[][] dp = new int[m][n];

for (int j=0; j<n; j++) {

dp[0][j] = sum[j+1];

}

for (int i=1; i<m; i++) {

for (int j=i; j<n; j++) {

int s = Integer.MAX_VALUE;

for (int k=0; k<j; k++) {

s = Math.min(s, Math.max(dp[i-1][k], sum[j+1] - sum[k+1]));

}

dp[i][j] = s;

}

}

return dp[m-1][n-1];

}

// DP 2

public int splitArray2(int[] nums, int m) {

int n = nums.length;

int[] sum = new int[n+1];

for (int j=1; j<=n; j++) sum[j] += sum[j-1] + nums[j-1];

int[] dp = new int[n];

for (int j=0; j<n; j++) {

dp[j] = sum[j+1];

}

for (int i=1; i<m; i++) {

int[] tmp = new int[n];

for (int j=0; j<n; j++) tmp[j] = dp[j];

for (int j=i; j<n; j++) {

int s = Integer.MAX_VALUE;

for (int k=0; k<j; k++) {

s = Math.min(s, Math.max(tmp[k], sum[j+1] - sum[k+1]));

}

dp[j] = s;

}

}

return dp[n-1];

}

// DP 3

public int splitArray3(int[] nums, int m) {

int n = nums.length;

int[] sum = new int[n+1];

for (int j=1; j<=n; j++) sum[j] += sum[j-1] + nums[j-1];

int[][] dp = new int[2][n];

for (int j=0; j<n; j++) {

dp[0][j] = sum[j+1];

}

for (int i=1; i<m; i++) {

for (int j=i; j<n; j++) {

int s = Integer.MAX_VALUE;

for (int k=0; k<j; k++) {

s = Math.min(s, Math.max(dp[(i+1)%2][k], sum[j+1] - sum[k+1]));

}

dp[i%2][j] = s;

}

}

return dp[(m+1)%2][n-1];

}

// Binary Search on Value Range

public int splitArray4(int[] nums, int m) {

int n = nums.length;

long l = Long.MIN_VALUE;

long r = 0;

for (int j=0; j<n; j++) {

l = Math.max(l, nums[j]);

r += nums[j];

}

while (l < r) {

long mid = (l + r) / 2;

int cnt = count(nums, m, mid);

if (cnt > m) {

l = mid + 1;

} else {

r = mid;

}

}

return (int) l;

}

private int count(int[] nums, int m, long mid) {

int res = 0;

long sum = 0;

for (int n: nums) {

sum += n;

if (sum > mid) {

res++;

sum = n;

}

}

return res+1;

}