改进了Project euler问题4的解决方案

Question

我在项目Euler中的问题4的StackOverflow中遇到了很多解决方案。我的问题不是再问一个已经在StackOverflow中实现的项目Euler的问题4的解决方案。相反，我遇到了改进的解决方案Improved solution by ROMANIA_engineer。我有两个问题反对改进的解决方案。无论如何，我已经发布了下面的解决方案，供人们调查。

public static void main(String[] args) {

int max = -1;

for ( int i = 999 ; i >= 100 ; i--) {
    if ( max >= i*999 ) { 
        break;
    }
    for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }
}       
System.out.println(max > -1? max : "No palindrome found");
}

问题

1. 为什么有条件（max> = i * 999）？通过包括如此廉价的操作，我们将实现什么目标？

从下面的片段，

for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }

2. 而不是j >= 100，它给了j >= i。我可以看到很多时间都被保存了，但是，我想知道背后的意图。

Answer 1

为了回答问题1，检查(max >= i * 999)的原因是你可能已经偶然发现两个3位数字的产品，这是一个回文，但大于i * 999。由于外部for循环从i = 999开始，一旦找到新的最大值，新的max有可能大于下一次迭代中递减的i值的最大可能回文乘积。例如，如果我们发现回文产品为926 * 998，其中i = 926且j = 998且新的最大值设定为该产品。请注意，这只是一个假设，我不知道该产品是否甚至是回文。然后内部for循环在迭代i = 926完成。然后在外部for循环的下一次迭代中，i现在是925，并且因为925 * 999小于926 * 998，所以不需要继续找到最大回文产品，因为它已被发现。原因是此时925 * 999是可以计算出来的最大可能的回文产品。

要回答问题2，j >= i的原因是为了避免重复产品的计算。例如，让我们说条件是j >= 100而不是。在内部for循环的第一次迭代时，当j为999且i也是999时。我们最终将计算产品从999 * 999,999 * 998，一直到999 * 100.但是，如果内在的话for循环到达了一个点，我现在是100而j是999，那么你最终会重复计算100 * 999.注意这只是一个例子，它甚至可能达不到这一点。