精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
2024年10月11号，上海格力汽车科技有限公司成立，注册资本2000万人民币，最大股东是珠海格力智能装备有限公司。经营范围含汽车零部件研发，汽车零部件及配件制造，工业机器人制造，工业机器人销售等。
对此网友质疑：格力跨界造车，但电动汽车的核心在于电池、电机和电控，这三大件格力是否有技术储备？毕竟跟空调还是差挺多的。
还有网友说：2000万够干嘛，研发一个轮子都够呛。不过2000万对于造车来说确实非常少。我在企查查上查了下小米汽车的注册资本是1000000万元人民币，蔚来汽车是300000万美元，基本上都是上百亿。
而格力2千万的注册资本估计勉强能招20个年薪百万的高级工程师，关键20个人在一年以内也造不出车啊，超过一年工资又不够发了。不过网友的评论也是相当幽默，基本都是调侃，大家可以看下。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第368题：最大整除子集。
问题描述
1，answer[i] % answer[j] == 0 ，或
2，answer[j] % answer[i] == 0
输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。
输入：nums = [1,2,4,8]
输出：[1,2,4,8]
1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 10^9
nums 中的所有整数互不相同
问题分析
public List<Integer> 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<Integer> res = new ArrayList<>();
while (maxIndex != -1) {
res.add(nums[maxIndex]);
maxIndex = path[maxIndex];
}
return res;
}
public:
vector<int> largestDivisibleSubset(vector<int> &nums) {
sort(nums.begin(), nums.end());// 先对数组进行排序
int n = nums.size();
vector<int> dp(n, 1);
vector<int> 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<int> res;
while (maxIndex != -1) {
res.push_back(nums[maxIndex]);
maxIndex = path[maxIndex];
}
return res;
}
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
数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap，哈夫曼树，滚动数组，差分数组，LRU缓存，LFU缓存
……
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓扑排序，约翰逊算法(Johnson)
……
