Description:

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.

Example:

Given nums = [1,2,3], return [1,2] or [1,3]

Given nums = [1,2,4,8], return [1,2,4,8]

Link:

http://www.lintcode.com/en/problem/largest-divisible-subset/

題目意思：

要求給出數(shù)組的一個(gè)子集，這個(gè)子集滿足
1.任意兩個(gè)數(shù)如a與b，a%b=0 或者 b%a=0。
2.這個(gè)子集盡可能大

解題思路：

首先有2個(gè)事實(shí)需要搞清楚：
1.任意兩個(gè)數(shù)當(dāng)a>b時(shí)，b%a是不等于0的，所以此題中任意兩個(gè)數(shù)只有a%b才可能為0；
2.當(dāng)有三個(gè)數(shù)a,b,c。滿足b%a=0, c%b=0時(shí)，則c%a=0。所以當(dāng)我們用一個(gè)數(shù)組來記錄數(shù)組中第i個(gè)數(shù)字a前面有dp[i]個(gè)數(shù)字滿足子集條件時(shí)，如果后面j位置數(shù)字b滿足b%a=0時(shí)，則狀態(tài)轉(zhuǎn)移方程由此得出：
dp[j] = dp[i] + 1

本道題得到每個(gè)數(shù)與之前的數(shù)可以組成的滿足要求子集的尺寸只是第一步，第二步是根據(jù)記錄的最大的那個(gè)數(shù)往前推出集合（所求答案）。

Time Complexity：

O(N^2)時(shí)間，O(N)空間

完整代碼：

vector<int> largestDivisibleSubset(vector<int>& nums) { vector<int> result; if(nums.size() == 0) return result; sort(nums.begin(), nums.end()); vector<int> dpSize(nums.size()); int maxSize = 1; int maxPoi = 0; for(int i = 0; i < nums.size(); i++) { bool find = false; for(int j = i-1; j >= 0; j--) { if(nums[i] % nums[j] == 0) { find = true; dpSize[i] = dpSize[j] + 1; break; } } if(!find) dpSize[i] = 1; if(dpSize[i] > maxSize) { maxSize = dpSize[i]; maxPoi = i; } } int bigger = nums[maxPoi]; for(int i = maxPoi; i >= 0; i--) { if(bigger % nums[i] == 0) { bigger = nums[i]; result.push_back(bigger); } } return result; }