第368题---largest divisible subset

• 题意描述
  • 给定一个不同的整数的数组，求他最长的可除的数组的长度（数组中的每两个数是可除的）
• 思路
  • 动态规划（懵逼了。）
• 代码

  class Solution {
  public:
      vector<int> largestDivisibleSubset(vector<int>& nums) {
          sort(nums.begin(), nums.end());
          
          vector<int> T(nums.size(), 0);
          vector<int> parent(nums.size(), 0);
          
          
          int m = 0;
          int mi = 0;
          
          for(int i = nums.size()-1; i >= 0; --i) {
              for(int j = i; j < nums.size(); ++j) {
                  if(nums[j] % nums[i] == 0 && T[i] < 1 + T[j]) {
                      T[i] = 1+T[j];
                      parent[i] = j;
                      if(T[i] > m) {
                          m = T[i];
                          mi = i;
                      }
                  }
              }
          }
          
          vector<int> ret;
          for(int i = 0; i < m; ++i) {
              ret.push_back(nums[mi]);
              mi = parent[mi];
          }
          return ret;
      }
  };