动态规划——最大整除子集C++

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> ans;
        if(nums.size() == 0)return ans;
        sort(nums.begin(), nums.end());
        int maxlen = 0;
        vector<int> longest(nums.size(), 1);
        vector<int> cnt(nums.size()+1, 0);
        cnt[nums.size()] = 0;
        for(int i = 1; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                if(nums[i] % nums[j] == 0){
                    if(longest[i] < longest[j] + 1)longest[i] = longest[j] + 1;
                }
            }
        }
        for(int i = 0; i < nums.size(); i++){
            if(cnt[longest[i]] == 0)cnt[longest[i]] = nums[i];
            if(maxlen < longest[i])maxlen = longest[i];
        }
        for(int i = 1; i <= maxlen; i++)ans.push_back(cnt[i]);
        return ans;
    }
};

int LCS(int *arr, int len){
    int longest[len], cnt[len];
    int maxlen = 0;
    for(int i = 0; i < len; i++){
        longest[i] = 1;
        cnt[i] = 0;
    }
    for(int i = 1; i < len; i++){
        for(int j = 0; j < i; j++){
            if(arr[i] > arr[j] && longest[i] < longest[j] + 1)
            longest[i] = longest[j] + 1;
        }
    }

    for(int i = 0; i < len; i++){
        if(cnt[longest[i]] == 0)cnt[longest[i]] = arr[i];
        if(longest[i] > maxlen)maxlen = longest[i];
    }
    for(int i = 1; i <= maxlen; i++)cout<<cnt[i]<<" ";
    cout<<endl;
    return maxlen;
}