格力也打算造车了。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

2024年10月11号，上海格力汽车科技有限公司成立，注册资本2000万人民币，最大股东是珠海格力智能装备有限公司。经营范围含汽车零部件研发，汽车零部件及配件制造，工业机器人制造，工业机器人销售等。

对此网友质疑：格力跨界造车，但电动汽车的核心在于电池、电机和电控，这三大件格力是否有技术储备？毕竟跟空调还是差挺多的。

还有网友说：2000万够干嘛，研发一个轮子都够呛。不过2000万对于造车来说确实非常少。我在企查查上查了下小米汽车的注册资本是1000000万元人民币，蔚来汽车是300000万美元，基本上都是上百亿。

而格力2千万的注册资本估计勉强能招20个年薪百万的高级工程师，关键20个人在一年以内也造不出车啊，超过一年工资又不够发了。不过网友的评论也是相当幽默，基本都是调侃，大家可以看下。

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

来看下今天的算法题，这题是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算法文档 。