368. Largest Divisible Subset

Level - medium

Task

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

• answer[i] % answer[j] == 0, or
• answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Объяснение

Дан массив целых чисел. Требуется найти подмножество этого массива, в котором каждый элемент делится на предыдущий элемент без остатка. При этом нужно найти такое подмножество, которое содержит максимально возможное количество элементов.

Формальное описание задачи:

• Дано: массив чисел nums.
• Найти: подмножество subset такое, что для каждой пары элементов a и b в subset, где a предшествует b, выполняется условие b % a == 0.
• Цель: максимизировать размер subset.

Пример:

• Вход: nums = [1, 2, 3, 4, 8]
• Выход: [1, 2, 4, 8]

Объяснение: В данном примере подмножество [1, 2, 4, 8] удовлетворяет условию, что каждый элемент делится на предыдущий. Это наибольшее возможное подмножество с таким свойством.

Для решения этой задачи можно использовать динамическое программирование. Основная идея заключается в сортировке массива и последующем построении наибольшего делимого подмножества с помощью запоминания наилучших решений для каждого элемента.

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 10^9
• All the integers in nums are unique.