/**
 * 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.
 *
 *
 *
 * 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.
 * @see <a href="https://leetcode.com/problems/largest-divisible-subset/">LeetCode</a>
 */
fun largestDivisibleSubset(nums: IntArray): List<Int> {
    val sortedNums = nums.sorted()
    val subsets = MutableList(sortedNums.size) { listOf<Int>() }
    var largestSubsetIndex = 0

    for ((index, num) in sortedNums.withIndex()) {
        var currentSubset = listOf(num)
        for (previousIndex in 0 until index) {
            val previousSubset = subsets[previousIndex]
            if (num % previousSubset.last() == 0 && previousSubset.size >= currentSubset.size) {
                currentSubset = previousSubset + num
            }
        }
        subsets[index] = currentSubset
        if (subsets[index].size > subsets[largestSubsetIndex].size) {
            largestSubsetIndex = index
        }
    }

    return subsets[largestSubsetIndex]
}

/**
 * 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.
 *
 *
 *
 * 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.
 * @see <a href="https://leetcode.com/problems/largest-divisible-subset/">LeetCode</a>
 */
fun largestDivisibleSubset(nums: IntArray): List<Int> {
    val sortedNums = nums.sorted()
    val subsets = MutableList(sortedNums.size) { listOf<Int>() }
    var largestSubsetIndex = 0

    for ((index, num) in sortedNums.withIndex()) {
        var currentSubset = listOf(num)
        for (previousIndex in 0 until index) {
            val previousSubset = subsets[previousIndex]
            if (num % previousSubset.last() == 0 && previousSubset.size >= currentSubset.size) {
                currentSubset = previousSubset + num
            }
        }
        subsets[index] = currentSubset
        if (subsets[index].size > subsets[largestSubsetIndex].size) {
            largestSubsetIndex = index
        }
    }

    return subsets[largestSubsetIndex]
}
