Как можно доказать правильность алгоритмов?

Для доказательства правильности алгоритмов можно использовать математическое доказательство, которое обычно состоит из следующих шагов:
1. Описание алгоритма и его работы.
2. Формулировка и доказательство инварианта - свойства, которое сохраняется на каждом шаге работы алгоритма.
3. Доказательство частных случаев - проверка работы алгоритма на различных входных данных.
4. Доказательство корректности - убедительное доказательство того, что алгоритм работает правильно для всех входных данных.
5. Оценка времени работы алгоритма.

Чтобы эффективно определить максимальное количество прямоугольников, которые можно вложить друг в друга по заданному условию, можно использовать методы динамического программирования. Необходимо создать подходящую матрицу или структуру данных, которая будет хранить информацию о прямоугольниках и их взаимном вложении. Затем можно написать алгоритм, который будет перебирать все возможные комбинации вложенных прямоугольников и выбирать оптимальный вариант. В конце концов, можно определить максимальное количество прямоугольников, которые можно вложить друг в друга, основываясь на результате работы алгоритма.

Если их нельзя переворачивать и при равенстве высот все-равно можно вложить (а не только строго меньшее), ио алгоритм правильный. Но доказательство не полное. Надо доказать, что любая неубывающая последовательность в этом массиве даст веладывающиеся прямоугольники.