package question;

import java.util.*;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question368 {
 public static void main(String[] args) {
 System.out.println(new Question368().largestDivisibleSubset(new int[]{
 832,33,531,416,335,298,365,352,582,936,366,305,930,530,97,349,71,295,840,108,299,804,925,627,953,571,658,732,429,136,563,462,666,330,796,315,695,500,896,982,217,200,912,98,297,612,169,943,628,593,959,904,219,240,857,789,897,940,569,384,502,382,401,184,716,230,29,963,211,597,515,122,163,86,215,105,889,842,49,847,267,87,954,407,245,975,719,746,709,471,281,238,186,510,618,149,73,214,663,194,260,825,631,474,519,668,329,718,765,947,156,353,490,962,679,560,59,387,31,692,976,568,201,273,159,730,819,418,906,801,892,672,559,866,389,675,812,744,164,737,57,195,115,933,158,909,598,359,853,314,983,11,395,153,781,301,838,625,704,256,351,996,225,644,521,509,674,417,272,622,937,723,632,331,228,412,181,435,469,157,368,524,38,132,325,420,127,731,771,604,505,634,67,374,894,3,448,878,686,641,316,207,76,363,795,235,770,446,820,493,177,816,615,410,117,944,829,190,831,289,516,964,170,134,671,885,682,119,402,82,485,901,375,68,858,739,56,974,683,884,815,872,715,104,290,348,588,834,788,472,466,867,550,779,65,802,459,440,870,753,608,808,623,642,44,437,865,758,540,506,691,958,854,546,39,595,369,504,63,311,722,441,786,899,338,651,874,946,811,848,939,284,824,309,653,133,514,460,678,54,399,759,468,61,480,783,266,900,400,237,403,534,213,914,473,198,380,373,288,154,844,535,409,249,285,168,69,345,647,851,846,264,102,246,106,648,576,212,438,981,987,379,360,667,95,172,101,580,891,385,747,161,927,361,818,657,171,342,232,734,714,362,425,475,28,41,551,142,131,51,229,9,607,326,522,687,792,845,665,358,91,720,155,565,99,26,650,539,780,589,950,935,372,227,424,750,833,554,841,552,60,757,430,916,140,790,426,776,96,199,923,806,949,755,711,659,911,611,310,774,265,880,690,706,761,286,255,756,204,444,478,601,529,669,241,784,566,528,208,270,511,236,271,378,58,453,467,233,250,567,296,932,989,367,626,35,162,887,572,603,564,797,280,406,970,689,408,431,638,489,85,50,357,803,47,555,793,422,763,110,869,861,253,320,538,347,405,769,64,875,630,537,328,553,166,948,303,160,800,507,920,922,90,693,636,17,455,183,210,856,762,656,174,873,579,176,688,640,1,938,902,341,740,581,427,111,972,443,22,791,304,574,575,725,477,700,817,381,479,248,121,411,547,182,871,599,203,13,224,541,724,178,775,388,4,251,321,52,88,100,279,614,839,84,151,735,40,752,773,376,77,476,708,396,988,961,24,231,445,609,952,965,986,414,451,881,42,257,32,334,130,596,527,94,333,317,244,960,710,852,862,421,81,37,452,274,187,268,520,491,778,18,743,620,145,72,370,118,748,633,997,436,143,573,495,180,34
 }));
 }
 public List<Integer> largestDivisibleSubset2(int[] nums) {
 Arrays.sort(nums);
 HashMap<Integer, List<Integer>> map = new HashMap<>();
 for (int num : nums) {
 boolean flag = false;
 for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
 if (num%entry.getKey()==0) {
 entry.getValue().add(num);
 flag = true;
 break;
 }
 }
 if (!flag) map.put(num, Arrays.asList(num));
 }
 Map.Entry<Integer, List<Integer>> max=null;
 for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
 if (max==null || entry.getValue().size()>max.getValue().size()) max=entry;
 }
 return max.getValue();
 }

 public List<Integer> largestDivisibleSubset_(int[] nums) {
 Arrays.sort(nums);
 int n = nums.length;
 int[] f = new int[n];
 int[] g = new int[n];
 for (int i = 0; i < n; i++) {
 // 至少包含自身一个数,因此起始长度为 1,由自身转移而来
 int len = 1, prev = i;
 for (int j = 0; j < i; j++) {
 if (nums[i] % nums[j] == 0) {
 // 如果能接在更长的序列后面,则更新「最大长度」&「从何转移而来」
 if (f[j] + 1 > len) {
 len = f[j] + 1;
 prev = j;
 }
 }
 }
 // 记录「最终长度」&「从何转移而来」
 f[i] = len;
 g[i] = prev;
 }

 // 遍历所有的 f[i],取得「最大长度」和「对应下标」
 int max = -1, idx = -1;
 for (int i = 0; i < n; i++) {
 if (f[i] > max) {
 idx = i;
 max = f[i];
 }
 }

 // 使用 g[] 数组回溯出具体方案
 List<Integer> ans = new ArrayList<>();
 while (ans.size() != max) {
 ans.add(nums[idx]);
 idx = g[idx];
 }
 return ans;
 }


 public List<Integer> largestDivisibleSubset(int[] nums) {
 Arrays.sort(nums);
 int[] dp=new int[nums.length];
 int[] first = new int[nums.length];
 for (int i = 0; i < first.length; i++) {
 first[i]=i;
 }
 Arrays.fill(dp, 1);
 for (int i = 1; i < dp.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;
 first[i]=j;
 }
 }
 }
 }
 int max=-1;
 int index=-1;
 for (int i = 0; i < dp.length; i++) {
 if (dp[i]>max) {
 max=dp[i];
 index=i;
 }
 }
 ArrayList<Integer> res = new ArrayList<>();
 while (res.size()<max) {
 res.add(nums[index]);
 index=first[index];
 }
 return res;
 }
}