最近在做Project Euler上面的一些题目，题目8是求一串数字序列的最大乘积。并举了一个序列的例子：
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
在这一千个数字中，四个相邻的数字的最大乘积是9 × 9 × 8 × 9 = 5832，现求13个相邻数字的最大乘积？
最开始以为这是一个二维数组，每一行数字相邻的有上下左右四个数字（边界条件下可能没有四个），所以设计了一种算法：从一个数字出发，加入到集合中，判断与集合相邻的数字中的最大者，并将其加入到集合中，如此反复扩充集合直至元素有13个。
代码如下：
1 public class Problem8 {
2 private static String[] digitNumbers =
3 {"73167176531330624919225119674426574742355349194934",
4 "96983520312774506326239578318016984801869478851843",
5 "85861560789112949495459501737958331952853208805511",
6 "12540698747158523863050715693290963295227443043557",
7 "66896648950445244523161731856403098711121722383113",
8 "62229893423380308135336276614282806444486645238749",
9 "30358907296290491560440772390713810515859307960866",
10 "70172427121883998797908792274921901699720888093776",
11 "65727333001053367881220235421809751254540594752243",
12 "52584907711670556013604839586446706324415722155397",
13 "53697817977846174064955149290862569321978468622482",
14 "83972241375657056057490261407972968652414535100474",
15 "82166370484403199890008895243450658541227588666881",
16 "16427171479924442928230863465674813919123162824586",
17 "17866458359124566529476545682848912883142607690042",
18 "24219022671055626321111109370544217506941658960408",
19 "07198403850962455444362981230987879927244284909188",
20 "84580156166097919133875499200524063689912560717606",
21 "05886116467109405077541002256983155200055935729725",
22 "71636269561882670428252483600823257530420752963450"};
23 private static int ROW = 20;
24 private static int COLUMN = 50;
25
26 public static void main(String[] args) {
27 //至顶向下的设计方法
28
29 //1.生成二维数组
30 int[][] numbers = generateNumbers(digitNumbers);
31
32 for (int i = 0; i < numbers.length; i++) {
33 if(i%5==0){
34 System.out.println();
35 }
36 for (int j = 0; j < numbers[i].length; j++) {
37 if(j%5==0){
38 System.out.printf(" ");
39 }
40 System.out.printf("%d ", numbers[i][j]);
41 }
42 System.out.println();
43 }
44
45 //2.遍历每一个元素，寻找当前元素所能找到的最优解
46 /**
47 * 思路如下：以某个元素为起点寻找最大乘积的过程如下：寻找该元素周围的最大数字，加入元素集合中，直至个数达到13个。
48 * 证明：如果某13个数字组成了最大乘积，那么其必然是某个元素起点按上述方法所能找到的集合
49 */
50 Long maxSum = 0L;
51 Set<Location> maxLocation = new HashSet<>();
52 List<Integer> maxValues=new ArrayList<>();
53 for (int i = 0; i < 1000; i++) {
54 int startIndexRow = i / COLUMN;
55 int startIndexColumn = i % COLUMN;
56 Set<Location> elementSet = new HashSet<>();
57 elementSet.add(new Location(startIndexRow, startIndexColumn));
58
59 while (true) {
60 //当set填充到13个元素时，终止执行
61 if (elementSet.size() >= 13) {
62 break;
63 }
64
65 //寻找周围的元素
66 List<Location> arounds = findAroundLocations(elementSet);
67
68 //找出数值最大的元素
69 Location currentMaxElement = findMaxElement(arounds, numbers);
70
71 //添加进set
72 elementSet.add(currentMaxElement);
73 }
74
75 //获取位置所在的元素的值
76 List<Integer> digits = getLocationValues(elementSet, numbers);
77 //System.out.println(elementSet.toString());
78
79 Long sum = 1L;
80 for (Integer digit : digits) {
81 sum *= digit;
82 }
83 if (sum > maxSum) {
84 maxSum = sum;
85 maxLocation = elementSet;
86 maxValues=digits;
87 }
88 }
89 System.out.println(maxSum);
90 for(Location loc:maxLocation){
91 System.out.println(loc.toString());
92 }
93 System.out.println(maxValues.toString());
94 return;
95 }
96
97 public static int[][] generateNumbers(String[] primitiveNumbers) {
98 int[][] result = new int[ROW][COLUMN];
99 for (int i = 0; i < primitiveNumbers.length; i++) {
100 String numbers = primitiveNumbers[i];
101 for (int j = 0; j < numbers.length(); j++) {
102 result[i][j] = Integer.parseInt(String.valueOf(numbers.charAt(j)));
103 }
104 }
105 return result;
106 }
107
108 /**
109 * 寻找周围的元素
110 *
111 * @param elementSet
112 * @return
113 */
114 private static List<Location> findAroundLocations(Set<Location> elementSet) {
115 List<Location> arounds = new ArrayList<>();
116 for (Location location : elementSet) {
117 //寻找单个元素周围的元素集
118 List<Location> locations = findSingleElementAroundLocations(location);
119 //周围的元素不能已经出现在集合中，如果在，则排除
120 for (Location loc : locations) {
121 if (!elementSet.contains(loc)) {
122 arounds.add(loc);
123 }
124 }
125 }
126 return arounds;
127 }
128
129 private static List<Location> findSingleElementAroundLocations(Location location) {
130 List<Location> aroundLocations = new ArrayList<>();
131 if (location.row - 1 >= 0) {
132 Location upLocation = new Location(location.row - 1, location.column);
133 aroundLocations.add(upLocation);
134 }
135 if (location.row + 1 < ROW) {
136 Location downLocation = new Location(location.row + 1, location.column);
137 aroundLocations.add(downLocation);
138 }
139 if (location.column - 1 >= 0) {
140 Location leftLocation = new Location(location.row, location.column - 1);
141 aroundLocations.add(leftLocation);
142 }
143 if (location.column + 1 < COLUMN) {
144 Location rightLocation = new Location(location.row, location.column + 1);
145 aroundLocations.add(rightLocation);
146 }
147 return aroundLocations;
148 }
149
150 private static List<Integer> getLocationValues(Set<Location> elementSet, int[][] numbers) {
151 List<Integer> result = new ArrayList<>();
152 for (Location loc : elementSet) {
153 int row = loc.row;
154 int column = loc.column;
155 Integer value = numbers[row][column];
156 result.add(value);
157 }
158 return result;
159 }
160
161 /**
162 * 寻找列表中元素最大的值所在的位置
163 *
164 * @param arounds：列表
165 * @param numbers：数字数组
166 * @return
167 */
168 private static Location findMaxElement(List<Location> arounds, int[][] numbers) {
169 Location result = arounds.get(0);
170 int row = result.row;
171 int column = result.column;
172 Integer value = numbers[row][column];
173 for (Location loc : arounds) {
174 row = loc.row;
175 column = loc.column;
176 Integer locValue = numbers[row][column];
177 if (locValue > value) {
178 value = locValue;
179 result = loc;
180 }
181 }
182 return result;
183 }
184
185
186 private static class Location {
187 private Integer row;
188 private Integer column;
189
190 public Location(int row, int column) {
191 this.row = row;
192 this.column = column;
193 }
194
195 @Override
196 public boolean equals(Object obj) {
197 if (this == obj) {
198 return true;
199 }
200 if (obj == null) {
201 return false;
202 }
203 if (obj instanceof Location) {
204 Location loc = (Location) obj;
205 if (loc.row == this.row && loc.column == this.column) {
206 return true;
207 }
208 }
209 return false;
210 }
211
212 @Override
213 public int hashCode() {
214 int result = 17;
215 result = 31 * result + (row == null ? 0 : row.hashCode());
216 result = 31 * result + (column == null ? 0 : column.hashCode());
217 return result;
218 }
219
220 @Override
221 public String toString() {
222 return "Location is:x=" + row + ",y=" + column;
223 }
224 }
225 }
226
结果发现这种方法求得的结果不对，看了别人的解题方法，才发现原来是理解错了。原数字串并不是一个二维数组而是一个一维数字串，所以求解方法就比较简单了。代码如下：
1 public class Problem8Ext {
2 private static String digitNumbers =
3 new String("73167176531330624919225119674426574742355349194934" +
4 "96983520312774506326239578318016984801869478851843" +
5 "85861560789112949495459501737958331952853208805511" +
6 "12540698747158523863050715693290963295227443043557" +
7 "66896648950445244523161731856403098711121722383113" +
8 "62229893423380308135336276614282806444486645238749" +
9 "30358907296290491560440772390713810515859307960866" +
10 "70172427121883998797908792274921901699720888093776" +
11 "65727333001053367881220235421809751254540594752243" +
12 "52584907711670556013604839586446706324415722155397" +
13 "53697817977846174064955149290862569321978468622482" +
14 "83972241375657056057490261407972968652414535100474" +
15 "82166370484403199890008895243450658541227588666881" +
16 "16427171479924442928230863465674813919123162824586" +
17 "17866458359124566529476545682848912883142607690042" +
18 "24219022671055626321111109370544217506941658960408" +
19 "07198403850962455444362981230987879927244284909188" +
20 "84580156166097919133875499200524063689912560717606" +
21 "05886116467109405077541002256983155200055935729725" +
22 "71636269561882670428252483600823257530420752963450");
23
24 public static void main(String[] args) {
25 //连续的13个数字相乘的最大乘积，并且数字仅仅是一串字符串
26 // Long maxNumber = 1L;
27 List<String> list = List.of(digitNumbers.split("0"));
28 Stream<Long> stream = Stream.ofAll(list)
29 .filter(str -> {
30 if (StringUtils.isNotBlank(str) && str.length() >= 13) {
31 return true;
32 }
33 return false;
34 })
35 .map(str -> {
36 Long maxMulti = 1L;
37 for (int i = 0; i < 13; i++) {
38 maxMulti *= Integer.parseInt(String.valueOf(str.charAt(i)));
39 }
40 Long tmpMulti = maxMulti;
41 for (int j = 13; j < str.length(); j++) {
42 Integer next = Integer.parseInt(String.valueOf(str.charAt(j)));
43 Integer last = Integer.parseInt(String.valueOf(str.charAt(j - 13)));
44 tmpMulti = tmpMulti * next / last;
45 if (tmpMulti > maxMulti) {
46 maxMulti = tmpMulti;
47 }
48 }
49 return maxMulti;
50 });
51 if (stream.isEmpty()) {
52 System.out.println(0);
53 } else {
54 System.out.println(stream.max().get());
55 }
56 }
57 }
