Wednesday, June 29, 2016

LeetCode 368 - Largest Divisible Subset

https://leetcode.com/problems/largest-divisible-subset/
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
```nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)
```
Example 2:
```nums: [1,2,4,8]

Result: [1,2,4,8]
```
https://www.hrwhisper.me/leetcode-largest-divisible-subset/
https://segmentfault.com/a/1190000005922634

1. 得到最大集合size
2. 输出这个集合

dp[i] = max(dp[i], dp[j] + 1), where 0<=j<i

注意

[1,2,4,8,9,72]

https://discuss.leetcode.com/topic/49652/classic-dp-solution-similar-to-lis-o-n-2
``````    public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
int[] count = new int[n];
int[] pre = new int[n];
Arrays.sort(nums);
int max = 0, index = -1;
for (int i = 0; i < n; i++) {
count[i] = 1;
pre[i] = -1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
if (1 + count[j] > count[i]) {
count[i] = count[j] + 1;
pre[i] = j;
}
}
}
if (count[i] > max) {
max = count[i];
index = i;
}
}
List<Integer> res = new ArrayList<>();
while (index != -1) {
index = pre[index];
}
return res;
}``````
https://discuss.leetcode.com/topic/49424/java-solution-in-32ms-o-n-2-time-o-n-space
http://www.bingfengsa.com/article/7kLzV8O

public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> ans = new ArrayList<Integer>();
if (nums.length == 0) return ans;
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n], index = new int[n];
Arrays.fill(dp, 1);
Arrays.fill(index, -1);
int max_index = 0, max_dp = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
index[i] = j;
}
}
if (max_dp < dp[i]) {
max_dp = dp[i];
max_index = i;
}
}
for (int i = max_index; i != -1; i = index[i])
return ans;
}

https://xuezhashuati.blogspot.com/2017/04/lintcode-603-largest-divisible-subset.html
```    public List<Integer> largestDivisibleSubset(int[] nums) {
int[] f = new int[nums.length];
int[] lastIndex = new int[nums.length];
Arrays.sort(nums);

int max = 0;
int maxIndex = -1;

for (int i = 0; i < nums.length; i++) {
f[i] = 1;
lastIndex[i] = -1;
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && f[i] < f[j] + 1) {
f[i] = f[j] + 1;
lastIndex[i] = j;
}
}
if (f[i] > max) {
max = f[i];
maxIndex = i;
}
}

List<Integer> result = new ArrayList<>();
while (maxIndex != -1) {
maxIndex = lastIndex[maxIndex];
}

return result;
}```
http://blog.csdn.net/qq508618087/article/details/51767785

https://xuezhashuati.blogspot.com/2017/04/lintcode-603-largest-divisible-subset.html
https://discuss.leetcode.com/topic/49424/java-solution-in-32ms-o-n-2-time-o-n-space
f[i]：以nums[i]作为Largest Divisible Subset的最后一个元素的集合的最大值。
lastIndex[i]：以nums[i]作为Largest Divisible Subset的最后一个元素的集合的上一个元素的index。
```    public List<Integer> largestDivisibleSubset(int[] nums) {
int[] f = new int[nums.length];
int[] lastIndex = new int[nums.length];
Arrays.sort(nums);

int max = 0;
int maxIndex = -1;

for (int i = 0; i < nums.length; i++) {
f[i] = 1;
lastIndex[i] = -1;
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && f[i] < f[j] + 1) {
f[i] = f[j] + 1;
lastIndex[i] = j;
}
}
if (f[i] > max) {
max = f[i];
maxIndex = i;
}
}

List<Integer> result = new ArrayList<>();
while (maxIndex != -1) {
maxIndex = lastIndex[maxIndex];
}

return result;
}```
The idea is to keep track of the next element in the array that gives the longest streak for each element in the array, then in the end, we find the start of the maximal streak, then start from there and find the rest of elements.
nextIdx is an array keeping track of the next element indexed j for each element at i that gives the longest streak, and maxLength keeps track of the current max length for each element. The core algorithm is: for each element at i, we go from n-1 to i+1 to find the best j, and we link i to jby specifying that nextIdx[i] = j.
After we have iterated every element, we start from the maxIdx, which points to the first element in the longest streak. We add that element to our result, then go to the next element according tonextIdx until we reach the last element in that streak, who will have value 0 in its nextIdx slot.
public List<Integer> largestDivisibleSubset(int[] nums) { if (nums.length == 0) { return new ArrayList<Integer>(); } int[] nextIdx = new int[nums.length]; int[] maxLength = new int[nums.length]; int max = 0, maxIdx = 0; Arrays.sort(nums); for (int i = nums.length - 1; i >= 0; i--) { maxLength[i] = 1; for (int j = nums.length - 1; j > i; j--) { if (nums[j] % nums[i] == 0) { if (maxLength[j] + 1 > maxLength[i]) { maxLength[i] = maxLength[j] + 1; nextIdx[i] = j; if (maxLength[i] > max) { maxIdx = i; } } } } } List<Integer> res = new ArrayList<Integer>(); res.add(nums[maxIdx]); int idx = nextIdx[maxIdx]; while (idx != 0) { res.add(nums[idx]); idx = nextIdx[idx]; } return res; }
utilize the transitivity of divisibility, kind of like " Longest Increasing Subsequence" problem However this one requires you to return the actual subset rather than cardinality of the set, so you need to do some bookkeeping by using another array.
https://leetcode.com/discuss/110927/concise-java-solution-using-dp-hashmap
public List<Integer> largestDivisibleSubset(int[] nums) { if(nums.length == 0) return (new ArrayList<Integer>()); Arrays.sort(nums); Map<Integer, Integer> map = new HashMap<>(); int[] dp = new int[nums.length], dp[0] = 1; int maxV = 1, index = 0; for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] % nums[j] == 0) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; map.put(nums[i], nums[j]); // backward index } if (dp[i] > maxV) { maxV = dp[i]; index = i; } } } } List<Integer> ret = new ArrayList<Integer>(); int key = nums[index]; ret.add(key); while (map.containsKey(key)) { ret.add(map.get(key)); key = map.get(key); } return ret; }
def largestDivisibleSubset(self, nums): """ :type nums: List[int] :rtype: List[int] """ nums = sorted(nums) size = len(nums) dp = [1] * size pre = [None] * size for x in range(size): for y in range(x): if nums[x] % nums[y] == 0 and dp[y] + 1 > dp[x]: dp[x] = dp[y] + 1 pre[x] = y idx = dp.index(max(dp)) ans = [] while idx is not None: ans += nums[idx], idx = pre[idx] return ans

def largestDivisibleSubset(self, nums): """ :type nums: List[int] :rtype: List[int] """ S = {-1: set()} for x in sorted(nums): S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x} return list(max(S.values(), key=len))

http://www.cnblogs.com/grandyang/p/5625209.html

```    vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> res;
vector<pair<int, int>> dp(nums.size());
int mx = 0, mx_idx = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i; j >= 0; --j) {
if (nums[i] % nums[j] == 0 && dp[i].first < dp[j].first + 1) {
dp[i].first = dp[j].first + 1;
dp[i].second = j;
if (mx < dp[i].first) {
mx = dp[i].first;
mx_idx = i;
}
}
}
}
for (int i = 0; i < mx; ++i) {
res.push_back(nums[mx_idx]);
mx_idx = dp[mx_idx].second;
}
return res;
}```

https://discuss.leetcode.com/topic/49455/4-lines-in-python
``````def largestDivisibleSubset(self, nums):
S = {-1: set()}
for x in sorted(nums):
S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
return list(max(S.values(), key=len))
``````
My `S[x]` is the largest subset with `x` as the largest element, i.e., the subset of all divisors of `x` in the input. With `S[-1] = emptyset`as useful base case. Since divisibility is transitive, a multiple `x` of some divisor `d` is also a multiple of all elements in `S[d]`, so it's not necessary to explicitly test divisibility of `x` by all elements in `S[d]`. Testing `x % d` suffices.
While storing entire subsets isn't super efficient, it's also not that bad. To extend a subset, the new element must be divisible by all elements in it, meaning it must be at least twice as large as the largest element in it. So with the 31-bit integers we have here, the largest possible set has size 31 (containing all powers of 2).
http://dartmooryao.blogspot.com/2016/06/leetcode-368-largest-divisible-subset.html
public List<Integer> largestDivisibleSubset(int[] nums) {
if(nums.length==0){ return new ArrayList<>(); }
Map<Integer, Integer> map = new HashMap<>();
Arrays.sort(nums);
int[] count = new int[nums.length];
Arrays.fill(count, 1);
int maxLen = 0;
int maxIdx = 0;
for(int i=nums.length-1; i>=0; i--){
for(int j=i+1; j<nums.length; j++){
if(nums[j]%nums[i]==0){
if(count[i] < count[j]+1){
count[i] = count[j]+1;
map.put(i, j);
}
}
}
if(count[i] > maxLen){
maxLen = count[i];
maxIdx = i;
}
}

List<Integer> result = new ArrayList<>();
Integer idx = maxIdx;
while(idx != null){
idx = map.get(idx);
}
return result;
}

If we need result sorted:
https://louisyw1.gitbooks.io/leetcode/content/dynamic_programming/largest_divisible_subset.html
``````        for(int i = 0; i < largest; i++){
res.insert(res.begin(), nums[last]);
last = son[last];
}
``````
``` for (int i = maxIdx; i >= 0;) { //回溯解集 res.addFirst(nums[i]); i = pre[i]; } ```

+
``````    vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());

vector<int> dp(nums.size(), 0);
vector<int> parent(nums.size(), 0);

int largest = 0;
int start = 0;
for(int i = nums.size() - 1; i >= 0; --i){
//此处j=i对应着上面将dp初始化为0；从后往前迭加，[1,2,4,5,8],效果为[8]->[4, 8]->[2, 4, 8]->[1,2,4,8]
for(int j = i; j < nums.size(); j++){
if(nums[j] % nums[i] == 0 && dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
parent[i] = j;
}

if(dp[i] > largest){
largest = dp[i];
start = i;
}
}

}

vector<int> res;

for(int i = 0; i < largest; i++){
res.push_back(nums[start]);
start = parent[start];
}
return res;
}``````
https://discuss.leetcode.com/topic/49563/using-hashmap-o-n-2-time-o-n-space

http://www.geeksforgeeks.org/largest-divisible-subset-array/
simple solution is to generate all subsets of given set. For every generated subset, check if it is divisible or not. Finally print the largest divisible subset.
An efficient solution involves following steps.
1. Sort all array elements in increasing order. The purpose of sorting is to make sure that all divisors of an element appear before it.
2. Create an array divCount[] of same size as input array. divCount[i] stores size of divisible subset ending with arr[i] (In sorted array). The minimum value of divCount[i] would be 1.
3. Traverse all array elements. For every element, find a divisor arr[j] with largest value of divCount[j] and store the value of divCount[i] as divCount[j] + 1.
Time Complexity : O(n2)
Auxiliary Space : O(n)
`void` `findLargest(``int` `arr[], ``int` `n)`
`{`
`    ``// We first sort the array so that all divisors`
`    ``// of a number are before it.`
`    ``sort(arr, arr+n);`
`    ``// To store count of divisors of all elements`
`    ``vector <``int``> divCount(n, 1);`
`    ``// To store previous divisor in result`
`    ``vector <``int``> prev(n, -1);`
`    ``// To store index of largest element in maximum`
`    ``// size subset`
`    ``int` `max_ind = 0;`
`    ``// In i'th iteration, we find length of chain`
`    ``// ending with arr[i]`
`    ``for` `(``int` `i=1; i<n; i++)`
`    ``{`
`        ``// Consider every smaller element as previous`
`        ``// element.`
`        ``for` `(``int` `j=0; j<i; j++)`
`        ``{`
`            ``if` `(arr[i]%arr[j] == 0)`
`            ``{`
`                ``if` `(divCount[i] < divCount[j] + 1)`
`                ``{`
`                    ``divCount[i] = divCount[j]+1;`
`                    ``prev[i] = j;`
`                ``}`
`            ``}`
`        ``}`
`        ``// Update last index of largest subset if size`
`        ``// of current subset is more.`
`        ``if` `(divCount[max_ind] < divCount[i])`
`            ``max_ind = i;`
`    ``}`
`    ``// Print result`
`    ``int` `k = max_ind;`
`    ``while` `(k >= 0)`
`    ``{`
`        ``cout << arr[k] << ``" "``;`
`        ``k = prev[k];`
`    ``}`
`}`