專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

網友爆料：華為od不裁員，干滿4年基本都續約了，就是干得越久和同期進來的正式員工薪資差距越大。另外，od的加班強度比較高。不過我的理解是od是勞務派遣，不存在裁不裁員，裁員是對正式員工的的一種行為。

十多年前我在銀行干過外包，如果任務多的時候銀行就會打電話讓外包公司送一些人過來，當然也不是送過來就要，還需要面試，面試之后合適的才會要。干個一年或半年，當活少的時候還會讓你回去，對于銀行來說這不叫裁員。回去之后你之前的公司還會把你外派到其他公司去干活，像這種頻繁的外派，員工的離職率非常高，除非是一些長期穩定的外派稍微好一些。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第368題：最大整除子集。

問題描述

來源：LeetCode第368題

難度：中等

給你一個由無重復正整數組成的集合 nums ，請你找出并返回其中最大的整 除子集 answer ，子集中每一元素對 (answer[i], answer[j]) 都應當滿足：

1，answer[i] % answer[j] == 0 ，或

2，answer[j] % answer[i] == 0

如果存在多個有效解子集，返回其中任何一個均可。

示例1：

輸入：nums = [1,2,3] 輸出：[1,2] 解釋：[1,3] 也會被視為正確答案。

示例2：

輸入：nums = [1,2,4,8] 輸出：[1,2,4,8]

• 1 <= nums.length <= 1000

• 1 <= nums[i] <= 2 * 10^9

• nums 中的所有整數互不相同

問題分析

這題讓找出最長的整除子集，注意這里是子集，不是子序列，所以我們可以對數組進行 排序 ，這樣這題就變成了我們前面講的 。按照前面那題的思路就可以解這道題了。

這里定義dp[i]表示以第 i 個元素為結尾的最長整除子集長度，如果nums[i]能被nums[j]整除(j

但這題讓返回的是子集，而不是子集的長度，所有我們還需要記錄選擇的過程，使用一個變量path來記錄最大的整除子集。

JAVA：

public List   largestDivisibleSubset (int[] nums)  {     Arrays.sort(nums);//  先對數組進行排序     int n = nums.length;     int[] dp = new int[n];     int[] path = new int[n];// 記錄最大整除子序列的下標     Arrays.fill(dp, 1); // 初始化數組dp的每個值為1     Arrays.fill(path, -1);// 初始 -1 。     int max = 1;// 記錄最大整除子集的長度     int maxIndex = 0;// 記錄最大整除子集中最后一個元素的下標     for (int i = 1; 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;                 // 記錄路徑，表示最大整除子集中 i 前面一個是 j                 path[i] = j;             }         }         // 如果找到更大的子集，就記錄最大的         if (dp[i] > max) {             max = dp[i];// 最大整除子集長度             maxIndex = i;// 最大整除子集最后一個元素的位置         }     }     // prev很類似于鏈表，每一個都是記錄前一個的位置     List
         
  res =  new ArrayList<>();      while (maxIndex != - 1) {         res.add(nums[maxIndex]);         maxIndex = path[maxIndex];     }      return res; }

C++：

public:     vector

  largestDivisibleSubset(vector

  &nums) {         sort(nums.begin(), nums.end());//  先對數組進行排序         int n = nums.size();         vector

  dp(n, 1);         vector

  path(n, -1);// 記錄最大整除子序列的下標         int max = 1;// 記錄最大整除子集的長度         int maxIndex = 0;// 記錄最大整除子集中最后一個元素的下標         for (int i = 1; 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;                     // 記錄路徑，表示最大整除子集中 i 前面一個是 j                     path[i] = j;                 }             }             // 如果找到更大的子集，就記錄最大的             if (dp[i] > max) {                 max = dp[i];// 最大整除子集長度                 maxIndex = i;// 最大整除子集最后一個元素的位置             }         }         // prev很類似于鏈表，每一個都是記錄前一個的位置         vector

  res;         while (maxIndex != -1) {             res.push_back(nums[maxIndex]);             maxIndex = path[maxIndex];         }         return res;     }

Python：

def largestDivisibleSubset(self, nums: List[int]) -> List[int]:     nums.sort()#  先對數組進行排序     n = len(nums)     dp = [1] * n     path = [-1] * n #記錄最大整除子序列的下標     max_len = 1 #記錄最大整除子集的長度     max_index = 0 #記錄最大整除子集中最后一個元素的下標     for i in range(1, n):         for j in range(i):             if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:                 dp[i] = dp[j] + 1                 path[i] = j #記錄路徑，表示最大整除子集中 i 前面一個是 j         # 如果找到更大的子集，就記錄最大的         if dp[i] > max_len:             max_len = dp[i] #最大整除子集長度             max_index = i # 最大整除子集最后一個元素的位置     res = []     # prev很類似于鏈表，每一個都是記錄前一個的位置     while max_index != -1:         res.append(nums[max_index])         max_index = path[max_index]     return res

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。