+/EE360C

algorithms

git clone https://git.julia.blue/+/EE360C

Joseph RyanRemove unnecessary prefilling of memoization array3424b96

master
3.1 KiB100 linesraw
1public class Program3 {
2    static int[][] sums;
3    static int[][] best;
4
5    static int sum(int start, int end) {
6        int temp = end;
7        while (sums[start][temp] == -1) { --temp; }
8        while (temp++ != end) {
9            sums[start][temp] = sums[start][temp - 1] + sums[temp][temp];
10        }
11        return sums[start][end];
12    }
13
14    static int diff(int l, int m, int r) {
15        int temp = Math.min(maximize(l, m) + sum(l, m),
16                            maximize(m + 1, r) + sum(m + 1, r));
17        return temp;
18    }
19
20    static int maximize_linear(int start, int end) {
21        if (best[start][end] != -1) {
22            return best[start][end];
23        }
24        int max = 0;
25        int max_index = -1;
26        int diff = 0;
27        for (int i = start; i < end; ++i) {
28            int left = maximize_linear(start, i) + sum(start, i);
29            int right = maximize_linear(i + 1, end) + sum(i + 1, end);
30            if ((diff = Math.min(left, right)) > max) {
31                max = diff;
32                max_index = i;
33            }
34        }
35        int left = maximize(start, max_index) + sum(start, max_index);
36        int right = maximize(max_index + 1, end) + sum(max_index + 1, end);
37        return best[start][end] = Math.min(left, right);
38    }
39
40    static int maximize(int start, int end) {
41        if (best[start][end] != -1) {
42            return best[start][end];
43        }
44        if (end - start == 1) {
45            return best[start][end] =
46                       Math.min(sums[start][start], sums[end][end]);
47        }
48        if (end - start <= 10) {
49            return maximize_linear(start, end);
50        }
51        int r = end;
52        int l = start;
53        int m = (r + l) / 2;
54        while (r - l > 1) {
55            int ldiff = diff(start, m - 1, end);
56            int mdiff = diff(start, m, end);
57            if (mdiff >= ldiff) {
58                int rdiff = diff(start, m + 1, end);
59                if (mdiff >= rdiff) {
60                    break;
61                }
62                l = m + 1;
63            } else {
64                r = m - 1;
65            }
66            m = (r + l) / 2;
67            if (m == l) {
68                mdiff = diff(start, m, end);
69                int temp = diff(start, m + 1, end);
70                if (temp > mdiff) {
71                    ++m;
72                }
73            }
74        }
75        int left = maximize(start, m) + sum(start, m);
76        int right = maximize(m + 1, end) + sum(m + 1, end);
77        return best[start][end] = Math.min(left, right);
78    }
79
80    public static int maxCoinValue(int[] cities) {
81        int n = cities.length;
82        sums = new int[n][n];
83        best = new int[n][n];
84        for (int i = 0; i < n; ++i) {
85            for (int j = 0; j < n; ++j) {
86                if (i == j) {
87                    sums[i][j] = cities[i];
88                    best[i][j] = 0;
89                } else {
90                    sums[i][j] = -1;
91                    best[i][j] = -1;
92                }
93            }
94        }
95        int total = 0;
96        int start = 0;
97        int end = n - 1;
98        return maximize(start, end);
99    }
100}