Улучшенное решение проблемы 4 от Project euler

Question

Я столкнулся с множеством решений в StackOverflow для задачи 4 в проекте Euler.Мой вопрос не о том, чтобы снова попросить решение проблемы 4 из проекта Euler, который уже реализован в StackOverflow.Вместо этого я наткнулся на улучшенное решение Улучшенное решение от 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;
        }
    }

Вместо j >= 100 ему дается j >= i.Я вижу, что сэкономлено много времени, однако я хотел узнать, что за этим стоит.

Answer 1

Для ответа на вопрос 1 причина проверки (max >= i * 999) состоит в том, что вы, возможно, уже наткнулись на произведение двух трехзначных чисел, которое является палиндромом, но больше i * 999.Поскольку внешний цикл for начинается с i = 999, после того как вы нашли новый максимум, есть вероятность, что новый максимум больше максимально возможного произведения палиндрома из уменьшенного значения 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 когда-либо достигнет точки, где i теперь равно 100, а j равно 999, тогда вы в конечном итоге повторите вычисления 100 * 999. Обратите внимание, что это всего лишь пример, он может даже не дойти до этой точки.