368. Largest Divisible Subset

LeetCode 368. Largest Divisible Subset

Description

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.

Tags

Math, Dynamic Programming

Solution

We first sort the input array so that we only need to evaluate nums[large]%nums[small] == 0 afterwards. We also initialize 2 arrays of length len(nums), to keep track of the longest subsequence at index i and its previous state. Iterating over nums, we first initialize the longest length and previous state with 1 and i respectively, then update both when nums[i]%nums[j] == 0 and find a longer sequence longLen[j]+1. After loop, we obtain the max length and its index, and collect all elements starting from such index along with states.

Complexity

• Time complexity: $O(n^2)$

• Space complexity: $O(n)$

Code

func largestDivisibleSubset(nums []int) []int {
	sort.Ints(nums) // sorted nums allows us to eval `nums[i]%nums[j] == 0` only
	ans, longLen, state := make([]int, 0, len(nums)), make([]int, len(nums)), make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		longLen[i], state[i] = 1, i // self
		for j := 0; j < i; j++ {
			if nums[i]%nums[j] == 0 && longLen[j]+1 > longLen[i] {
				longLen[i], state[i] = longLen[j]+1, j
			}
		}
	}
	var maxLen, maxIdx int
	for i, l := range longLen {
		if l > maxLen {
			maxLen, maxIdx = l, i
		}
	}
	for len(ans) != maxLen {
		ans = append(ans, nums[maxIdx])
		maxIdx = state[maxIdx] // backtrace
	}
	return ans
}

Reference

1. 详解为何能转换为序列 DP 问题