給一組不同的正整數 nums，要找出滿足條件 s[i]%s[j]==0 or s[j]%s[i]==0 之最大的集合
這題要回傳的是「最大的集合」，所以需要先知道最大的，然後再回頭生成。
要滿足條件，大的一定要是次大的乘以某整數，這樣才能歸納於同一組，同時也符合餘數的條件。
我卡了很久，因為我一直想突破 O(N^2) 的障礙，要是想到 O(N^2) 的方法就不會去嘗試，而且對於這樣的題目被太多種DP衍生的可能給卡住。
大概花了二天，才完成我的理想型，也是最初設想的數學理論版。要把想法變成方法就是難度所在，也是樂趣所在。
一個排列過的最大集合，最大的一定是其左一個乘上某數，即「因數」。而一個數的左方會接子集合有最大數目的因數。
將 nums 先 sort() 過，接下來用 for 就會是而小至大的 num 。
比較的是「數目」，因此要保存每個數的最大可能數目，用 count 保存，每個數至少會有 1 即自身。
然而這題要的是最大數目的集合，所以不只要找出數目有多少，也要有能得到最大數目集合有哪些元素的手段。
一種是把所有可能取出來，再從中找到數目最大即可。二是弄成關聯的形式，再從最大數目的某一資訊去回溯出最大的集合。
走方案一比較直觀，但是會用上大量的記憶體，也比方案二慢。
選擇方案二，弄個關聯 path ，如果自身的因數在 nums 裡，那麼會從中選有最大數目集合的因數跟自身組合。
那個因數也是如此進行，直到找不到除了自身之外任何有在 nums 的因數。
如︰[1,2,4,8]，對 8 而言是 4 ，對 4 而言是 2 ，對 2 而言是 1 ，對 1 而言沒有，所以就停止，過程回溯了最大數目集合的所有元素。
因此，在初始化的時候，每個數字的預設即為自身，如果有找到其它的因數在 nums 中，再去選擇有最大數目的因數 。
於是變成，對 1 而言是 1，所以就停止。(預期path = {1:1, 2:1, 4:2, 8:4})
確立了關聯，但要能回溯出來最大集合，一定要有最大數目集合的最大數值。 所以一旦當前 num 的最大數目是比紀錄更高，就把數字保存下來。
可能最大數目相同的集合會有二種以上，但哪一種都沒有關係，取一就好。
這題與其他題不一樣的是，合法的規則都建立在「因數」上，所以用因數的算法是最合理的，而不是從 nums 去一對對試 s[i]%s[j]==0 or s[j]%s[i]==0 。
因數的找法是從左右界找尋，左界預設為 1，右界預設為 nums[i]，下一輪，左界 + 1 為 2，右界為 nums[i]/2(左界) ，如果右界沒有整除，左界就繼續 + 1，右界為 nums[i]/左界。
這個找法會用上 O(N**(1/2)) Time ，然後所有元素都這樣用，整體會是 O(N**(3/2)) Time， 比起一對對試的 O(N**2) 是更快速的。
Python
class Solution:
def largestDivisibleSubset(self, nums):
if not nums: return nums
nums.sort()
count = dict([(num, 0) for num in nums])
path = dict([(num, num) for num in nums])
max_num, max_count = nums[0], 0
for num in nums:
l = 1
r = num
while l <= r:
if r in path and count[r]+1 > count[num]:
count[num] = count[r]+1
path[num] = r
if l in path and count[l]+1 > count[num]:
count[num] = count[l]+1
path[num] = l
l += 1
while l <= r and num / l % 1 != 0:
r = num / l
l += 1
r = num // l
if max_count < count[num]:
max_num, max_count = num, count[num]
result = [max_num]
while path[max_num] != max_num:
max_num = path[max_num]
result.append(max_num)
return result
C#
public class Solution {
public IList LargestDivisibleSubset(int[] nums) {
var result = new List();
if(nums.Length == 0){return result;}
Array.Sort(nums);
var path = new Dictionary();
var count = new Dictionary();
for(int i = 0; i < nums.Length; i++)
{
int num = nums[i];
path[num] = num;
count[num] = 0;
//
int l = 1;
int r = num;
while(l <= r)
{
if(path.ContainsKey(l) && count[l] + 1 > count[num])
{
count[num] = count[l] + 1;
path[num] = l;
}
if(path.ContainsKey(r) && count[r] + 1 > count[num] && r != num && r != l)
{
count[num] = count[r] + 1;
path[num] = r;
}
l += 1;
r = num/l;
while(l 0)
{
l += 1;
r = num/l;
}
}
}
int maxNum = count.Aggregate((x, y) => x.Value > y.Value ? x : y).Key;
result.Add(maxNum);
while(path[maxNum] != maxNum)
{
maxNum = path[maxNum];
result.Add(maxNum);
}
return result;
}
}