0368. Largest Divisible Subset (Medium)
寫在前面
容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/2desolve
「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/adesolve
Question
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
| |
Example 2
| |
分析/解題
給定一個內含不同正整數的集合，找出最大的子集合，使得當中任取一對元素(Si, Sj)出來均能符合Si整除Sj或Sj整除Si。
如果有多個不同的解，回傳當中任何一個都可以。
首先我們可以先想到，在這個題目當中顯然nums是沒有被排序的，
如果以最笨的辦法來說的話，一個集合會擁有2^N個子集合
(因為每個元素都可以選擇要在這個子集合或不在這個子集合內)，
而每個組合當中如果又要兩兩檢查的話，又要各自花上n(n-1)/2的時間。
(n為該子集合的元素數量)
顯然直接考慮是非常不符合的，所以只好嘗試先排序過後，
看看能得到什麼可以用的特性。
那在排序過後，我們會想到一個點是，如果我們由小到大看的話，
假設前面選取了a跟b，那下一個選取的數c只需要確定能被b整除即可。
為什麼？因為按順序由小到大排，所以當我們選b的時候，
一定是要b能被a整除才行，於是後面接續的選擇，
只要確保能被最後一個數整除，就會符合能被前面的其他數整除了！
接著下來，假設我們觀察一下數列的規律：
假設有一個數列是1, 2, 3, 4, 6, 8, 12, 18，
我們可以稍微列出幾串能成立Divisible Subset的內容
(先不考慮有沒有最大個數)：
1, 2, 4 , 8
1, 3, 6, 12
1, 3, 6, 18
1, 2 , 6, 12
1, 2, 6, 18
有沒有發現，當中間選的不一樣，後面能接的數字也就不一樣，
從最大的數字往回推的時候，上一個index就有可能因而改變。
由於我們在考慮的是如何去找前面已經選取的子集合，
和下面要選取的數的關係，所以這基本上就是動態規劃的題目跑不了XD!
那麼，該怎麼樣定這中間的關係呢？
首先選取我們的dp，這個值要能夠拿來比較哪個子集合是擁有最多元素的，
那我們不妨這麼定義：
dp[i]就是從已經排序好的nums中，從index 0~i的數字中，
選取出來最大可整除的子集合其元素的個數，且這個子集合當中必須包含nums[i]。為什麼要定義必須包含nums[i]呢？因為不管怎麼樣，
最起碼可以選取index i，這樣子我們就可以將所有dp[i]先初始化為1 ，
因為這是它的保底。
接下來，我們要怎麼去紀錄當確立一個子集合的時候，
整個子集合的長相呢？
可以利用每個比較大的數只需要看前面一個數是否能將其整除的特性，
定義一組陣列或串列，當中存放符合前面dp定義的時候，
nums[i]的對應到前面一個數的index在哪裡 ，
將其稱呼為lidx(last index)。我們在找到最大的解的時候，
後續可以利用lidx來列出整個解。因此，將lidx全部初始化為-1 ，
當我們最後迴圈找尋遇到-1的時候，就表示整個解都被我們列出來了。
那接下來就簡單了，定義一個全局最大解所在的索引值max_idx，
以及最大解的元素總數max_dp，分別初始化成0跟1。
接下來我們需要一個雙層的迴圈，第一層迴圈是i從0開始到nums尾端 ，
以nums[i]做為當下這個子集合的最大值。
而第二層迴圈則是j從i-1開始到0 ，
目的是要一路往回找nums[i]是否整除nums[j]。
如果整除的話，代表有一個子集合的排列方式是：
…… , nums[j], nums[i]
這個子集合是不是對i來說是最好的狀況呢？
那就要看dp[j]+1是不是比dp[i]還要大 ，
如果比較大，才表示i的排列要換成走j這條線對吧XD？
所以比較大 的話，我們就應該要把dp[i]的值改成dp[j] + 1 ，
並且lidx[i]要改成j (因為改成走nums[j]這條路了)。
每次將j走完以後，dp[i]有可能被改變，
自然全局最大的解也有可能被改變，所以我們要檢查看看，
如果需要更動，就進行更動。
如此完成了雙層迴圈後，
最後就從max_idx開始以一個單層迴圈將解列出來 ，
記得迴圈的結束條件是index碰到-1 (代表已經到頭了)。
依此，寫成程式碼如下：
Java
Java的部分，可以用Arrays.fill來進行填充初始值的動作，
其他則是使用ArrayList來將res一個一個加入(要用LinkedList也可以)。
最後一個for迴圈的部分，如果使用者不想留max_idx，
也可以直接使用while來操作，
每次的下一步則是max_idx = lidx[max_idx] 。
Python
Python的部分則是用[x] * n的方式來初始化，其他的部分跟Java並無不同。
請留意將串列原地排要用nums.sort() ，
如果用sorted(nums) 的話則是會回傳一個新的排序好的串列 。
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(N²)/O(N)，因為時間用到雙層迴圈，每層都是O(N)要相乘，
而O(N²)會大於排序用的O(NlogN)，所以就取O(N²)；
空間上則用到dp跟lidx，均為O(N))
相似及延伸
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve