LeetCode 368. 最大整除子集（DP）

示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)

示例 2:
输入: [1,2,4,8]
输出: [1,2,4,8]

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.empty()) return {};
    	sort(nums.begin(), nums.end());
    	int i, j, n = nums.size();
    	int maxlen = 1, maxlenid = 0;
    	vector<pair<int,int>> dp(n);//到该位置的最大长度，前一个idx
    	for(i = 0; i < n; ++i)
    		dp[i] = make_pair(1, -1);
    	for(i = 1; i < n; ++i)
    	{
    		for(j = i-1; j >= 0; --j)
    		{
    			if(nums[i]%nums[j] == 0 && dp[j].first+1 > dp[i].first)
    			{
    				dp[i].first = dp[j].first + 1;//最大长度
    				dp[i].second = j;//前一个数的idx
    			}
    		}
    		if(dp[i].first > maxlen)
    		{
    			maxlen = dp[i].first;//最大长度
    			maxlenid = i;//最大长度的结束数字
    		}
    	}
    	vector<int> ans(maxlen);
    	ans[maxlen-1] = nums[maxlenid];//最后一个数字
    	for(i = maxlen-2; i >= 0; --i)
    	{
    		ans[i] = nums[dp[maxlenid].second];//前一个数字
    		maxlenid = dp[maxlenid].second;//向前递推
    	}
    	return ans;
    }
};