Leetcode 368. Largest Divisible Subset solution

Problem statement could be found @https://leetcode.com/problems/largest-divisible-subset/

Approach -

For every element n, check previous (n-1) elements and see if there modulo is zero. Whenever modulo is zero, store the chain length and index for the max value



Solution

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
       
        if (nums.size() <=1){
            return nums;
        }
       
        sort(nums.begin(), nums.begin() + nums.size());
        int *indexArr = new int[nums.size()];
        int *sizeArr = new int[nums.size()];
       
        for(int i=0;i<nums.size();i++){
            indexArr[i] = i;
            sizeArr[i] = 0;
        }
        int maxSize = 0;
        int maxIndex = 0;
        for(int i=0;i<nums.size();i++){
            for (int j=i-1;j>=0;j--){
                if ((nums[i]%nums[j]) == 0){
                    if (sizeArr[i] < (sizeArr[j] +1)){
                        sizeArr[i] = sizeArr[j] + 1;
                        indexArr[i] = j;
                        if (maxSize < sizeArr[i]){
                            maxSize = sizeArr[i];
                            maxIndex = i;
                        }
                    }
                   
                }
            }
        }
        vector<int> retVal;
        while (indexArr[maxIndex] != maxIndex){
            retVal.push_back(nums[maxIndex]);
            maxIndex = indexArr[maxIndex] ;
        }
        retVal.push_back(nums[maxIndex]);
        vector<int> opRetVal;
       
       for (int i=retVal.size()-1;i>=0;i--){
            opRetVal.push_back(retVal[i]);
        }
        return opRetVal;
    }
};