I was curious to see another post and tried it myself. The problem is
"1000 numbers are lined up. Take 13 consecutive numbers from them and consider the product of those 13 numbers. Find the maximum value."
something like.
It would be a hindrance to have 13 multiplications done nearly 1000 times, and if you think of it as a scale method, division would occur nearly 1000 times, which is not good. Let's use ** logarithm ** because we take a lot of products. $ \ log_a M $ is called the logarithm of $ M $ with ** $ a $ as the base **, and is defined as follows.
Real number r,a>0, a\neq1,M>Against 0\\
a^r=M \iff r= \log_a M
Simply put, it represents the exponent when trying to represent the positive number $ M $ as a power of a non-one positive number $ a $. For example, $ 2 ^ 3 = 8 $, so $ \ log_2 8 = 3 $. Also, consider expanding the exponent to the entire real number. Based on this idea, it becomes $ 2 ^ {\ frac {1} {2}} = \ sqrt {2} $, so it becomes $ \ log_2 \ sqrt {2} = \ frac {1} {2} $.
The exponential law $ a ^ x \ times a ^ y = a ^ {x + y} $ holds for the exponent. From the standpoint that the index is originally the number of multiplications, it seems natural to understand that those multiplications are multiplied by the total number of multiplications. This is a logarithmic expression.
a>0, a\neq1,M>0,N>Against 0\\
\log_a {MN} = \log_a M + \log_a N
Due to this property, ** multiplication can be converted to logarithmic addition. ** Also logarithmic
M>0,N>Set to 0.\\
a>When 1, M<N \iff \log_a M < \log_a N
It has the property of. In other words, when $ a> 1 $, the magnitude of the original number matches the magnitude of the logarithm. ** Using this, multiplication is used as logarithmic addition, and it is calculated by searching for the interval where the sum of logarithms is maximized by the scale method.
To take the logarithm this time, we use the method Math.log10 (x) of the Java Math class. It is a method that takes the logarithm of the argument with $ a = 10 $, that is, finds $ \ log_ {10} x $.
(By the way, the logarithm taken as $ a = 10 $ is called ** common logarithm **.)
Since the required logarithm is only for each of the 10 numbers from 0 to 9, calculate it in advance and put it in the array. However, the logarithm for 0 is not mathematically defined, and the method definition is "negative infinity", so if this is added by the scale method, it cannot be undone. Therefore, -1000 is set as the logarithm to 0 for convenience. As a result, the sum of logarithms will always be negative in the section containing 0, and it will be out of the maximum candidate, and it will be possible to restore it when 0 is out.
Once the maximum interval is known, the product is actually calculated. This is because if you try to find it from the definition of logarithm, you may not get an accurate value due to the problem of floating point error.
The code written with that idea is as follows.
import java.util.*;
import java.util.stream.*;
public class Main {
private static final String NUMS
= "73167176531330624919225119674426574742355349194934"
+ "96983520312774506326239578318016984801869478851843"
+ "85861560789112949495459501737958331952853208805511"
+ "12540698747158523863050715693290963295227443043557"
+ "66896648950445244523161731856403098711121722383113"
+ "62229893423380308135336276614282806444486645238749"
+ "30358907296290491560440772390713810515859307960866"
+ "70172427121883998797908792274921901699720888093776"
+ "65727333001053367881220235421809751254540594752243"
+ "52584907711670556013604839586446706324415722155397"
+ "53697817977846174064955149290862569321978468622482"
+ "83972241375657056057490261407972968652414535100474"
+ "82166370484403199890008895243450658541227588666881"
+ "16427171479924442928230863465674813919123162824586"
+ "17866458359124566529476545682848912883142607690042"
+ "24219022671055626321111109370544217506941658960408"
+ "07198403850962455444362981230987879927244284909188"
+ "84580156166097919133875499200524063689912560717606"
+ "05886116467109405077541002256983155200055935729725"
+ "71636269561882670428252483600823257530420752963450";
public static void main(String[] args) {
final int SPAN = 13;
final double[] log10 = IntStream.range(0, 10).mapToDouble(Math::log10).toArray();
log10[0] = -1000;
double logMax = IntStream.range(0, SPAN).mapToDouble(i -> log10[getNum(i)]).sum();
int head = 0;
double partial = logMax;
for (int i = 0, j = SPAN; j < NUMS.length(); i++, j++) {
partial = partial - log10[getNum(i)] + log10[getNum(j)];
if (partial > logMax) {
logMax = partial;
head = i + 1;
}
}
long result = IntStream.range(head, head + SPAN)
.mapToLong(i -> getNum(i))
.reduce(1L, (x, y) -> x * y);
System.out.println(result);
}
private static int getNum(int i) {
return NUMS.charAt(i) - '0';
}
}