public class Program3 { static int[][] sums; static int[][] best; static int sum(int start, int end) { int temp = end; while (sums[start][temp] == -1) { --temp; } while (temp++ != end) { sums[start][temp] = sums[start][temp - 1] + sums[temp][temp]; } return sums[start][end]; } static int diff(int l, int m, int r) { int temp = Math.min(maximize(l, m) + sum(l, m), maximize(m + 1, r) + sum(m + 1, r)); return temp; } static int maximize_linear(int start, int end) { if (best[start][end] != -1) { return best[start][end]; } int max = 0; int max_index = -1; int diff = 0; for (int i = start; i < end; ++i) { int left = maximize_linear(start, i) + sum(start, i); int right = maximize_linear(i + 1, end) + sum(i + 1, end); if ((diff = Math.min(left, right)) > max) { max = diff; max_index = i; } } int left = maximize(start, max_index) + sum(start, max_index); int right = maximize(max_index + 1, end) + sum(max_index + 1, end); return best[start][end] = Math.min(left, right); } static int maximize(int start, int end) { if (best[start][end] != -1) { return best[start][end]; } if (end - start == 1) { return best[start][end] = Math.min(sums[start][start], sums[end][end]); } if (end - start <= 10) { return maximize_linear(start, end); } int r = end; int l = start; int m = (r + l) / 2; while (r - l > 1) { int ldiff = diff(start, m - 1, end); int mdiff = diff(start, m, end); if (mdiff >= ldiff) { int rdiff = diff(start, m + 1, end); if (mdiff >= rdiff) { break; } l = m + 1; } else { r = m - 1; } m = (r + l) / 2; if (m == l) { mdiff = diff(start, m, end); int temp = diff(start, m + 1, end); if (temp > mdiff) { ++m; } } } int left = maximize(start, m) + sum(start, m); int right = maximize(m + 1, end) + sum(m + 1, end); return best[start][end] = Math.min(left, right); } public static int maxCoinValue(int[] cities) { int n = cities.length; sums = new int[n][n]; best = new int[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) { sums[i][j] = cities[i]; best[i][j] = 0; } else { sums[i][j] = -1; best[i][j] = -1; } } } int total = 0; int start = 0; int end = n - 1; return maximize(start, end); } }