368. Largest Divisible Subset

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public IList<int> LargestDivisibleSubset(int[] nums) {
        int n = nums.Length;
        if (n == 0) return new List<int>();
        Array.Sort(nums);
        List<List<int>> EDS = new List<List<int>>(new List<int>[n]);
        for (int i = 0; i < n; i++) {
            EDS[i] = new List<int>();
        }
        for (int i = 0; i < n; i++) {
            List<int> maxSubset = new List<int>();
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0 && maxSubset.Count < EDS[k].Count) {
                    maxSubset = EDS[k];
                }
            }
            EDS[i] = new List<int>(maxSubset);
            EDS[i].Add(nums[i]);
        }
        List<int> ret = new List<int>();
        foreach (var subset in EDS) {
            if (ret.Count < subset.Count) {
                ret = subset;
            }
        }
        return ret;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> LargestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return new List<int>();
        sort(nums.begin(), nums.end());
        List<List<int>> EDS = new List<List<int>>(new List<int>[n]);
        for (int i = 0; i < n; i++) {
            EDS[i] = new List<int>();
        }
        for (int i = 0; i < n; i++) {
            List<int> maxSubset = new List<int>();
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0 && maxSubset.size() < EDS[k].size()) {
                    maxSubset = EDS[k];
                }
            }
            EDS[i] = new List<int>(maxSubset);
            EDS[i].push_back(nums[i]);
        }
        List<int> ret = new List<int>();
        foreach (var subset in EDS) {
            if (ret.size() < subset.size()) {
                ret = subset;
            }
        }
        return ret;
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();

        Arrays.sort(nums);
        List<List<Integer>> EDS = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            EDS.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            List<Integer> maxSubset = new ArrayList<>();
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0 && maxSubset.size() < EDS.get(k).size()) {
                    maxSubset = EDS.get(k);
                }
            }
            EDS.get(i).addAll(maxSubset);
            EDS.get(i).add(nums[i]);
        }

        List<Integer> ret = new ArrayList<>();
        for (List<Integer> subset : EDS) {
            if (ret.size() < subset.size()) {
                ret = subset;
            }
        }
        return ret;
    }
}

class Solution {
    largestDivisibleSubset(nums) {
        const n = nums.length;
        if (n === 0) return [];

        nums.sort((a, b) => a - b);
        const EDS = Array.from({ length: n }, () => []);

        for (let i = 0; i < n; i++) {
            let maxSubset = [];
            for (let k = 0; k < i; k++) {
                if (nums[i] % nums[k] === 0 && maxSubset.length < EDS[k].length) {
                    maxSubset = EDS[k];
                }
            }
            EDS[i] = [...maxSubset, nums[i]];
        }

        let ret = [];
        for (const subset of EDS) {
            if (ret.length < subset.length) {
                ret = subset;
            }
        }
        return ret;
    }
}

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n == 0:
            return []

        nums.sort()
        EDS = [[] for _ in range(n)]

        for i in range(n):
            maxSubset = []
            for k in range(i):
                if nums[i] % nums[k] == 0 and len(maxSubset) < len(EDS[k]):
                    maxSubset = EDS[k]

            EDS[i] = maxSubset + [nums[i]]

        ret = []
        for subset in EDS:
            if len(ret) < len(subset):
                ret = subset
        return ret

package main

import (
  "fmt"
  "sort"
)

func largestDivisibleSubset(nums []int) []int {
  n := len(nums)
  if n == 0 {
    return []int{}
  }

  sort.Ints(nums)
  EDS := make([][]int, n)

  for i := 0; i < n; i++ {
    maxSubset := []int{}
    for k := 0; k < i; k++ {
      if nums[i]%nums[k] == 0 && len(maxSubset) < len(EDS[k]) {
        maxSubset = EDS[k]
      }
    }
    EDS[i] = append([]int{}, maxSubset...)
    EDS[i] = append(EDS[i], nums[i])
  }

  ret := []int{}
  for _, subset := range EDS {
    if len(ret) < len(subset) {
      ret = subset
    }
  }
  return ret
}

func main() {
  nums := []int{1, 2, 4, 8}
  fmt.Println(largestDivisibleSubset(nums))
}

Algorithm

Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4).

Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8).

Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}.

😎