LeetCode日本語修行10日目- [368-最大整除部分集合]

###Largest Divisible Subset
#####参考：https://leetcode.com/problems/largest-divisible-subset/
###問題の内容:
正の整数集合nums、それぞれの要素が相異、この中に(answer[i], answer[j])の条件を満足するような最大の部分集合answerを返す。
(answer[i], answer[j])の条件:
answer[i] % answer[j] == 0, または
answer[j] % answer[i] == 0
複数の解がある場合は、そのうちどちらも正しいです。
###例:
例1:
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

例2:
Input: nums = [1,2,4,8]
Output: [1,2,4,8]
###ヒント:
1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 109
All the integers in nums are unique.

---

このような問題は、基本的DPを使います。今回は
必要の条件は、現在の要素の最大整除部分集合 maxSizeを貰います。
たとえ：
1 2 4 6 8 9
1: 1 ->1
2: 1,2 -> 2
4: 1,2,4 -> 3
6: 1,2,6 -> 3
8: 1,2,4,8 -> 4
9: 1,9 -> 2
1 2 4 6 8 9
1 2 3 3 4 2
そして、最大の8の中に、必ず4,2,1を含めます。

if(nums[i] % nums[j]　== 0 && nums[j] % nums[k] == 0){
   nums[i] % nums[k] == 0
}

DPの形になりました。
貰ったmaxSizeを格納のdpArrayをトラバーサルして、maxSize対応のvalueを順番で渡す

class Solution {
    fun largestDivisibleSubset(nums: IntArray): List<Int> {
        var size = nums.size
        var dpArray = IntArray(size){1}
        var maxSize = 1
        var maxValue = dpArray[0]

        nums.sort()

        for(i in 1 until size){
            for(j in 0 until i){
                if(nums[i] % nums[j] == 0){
                    dpArray[i] = Math.max(dpArray[i],dpArray[j]+1)
                }
            }
            if(dpArray[i] > maxSize){
                maxSize = dpArray[i]
                maxValue = nums[i]
            }
        }

        var answer: MutableList<Int> = mutableListOf()

        if(maxSize == 1){
            answer.add(nums[0])
            return answer
        }

        var index = size-1
        
        while(index >= 0 && maxSize > 0){
            if(dpArray[index] == maxSize && maxValue % nums[index] == 0){
                answer.add(nums[index])
                maxValue = nums[index]
                maxSize--
            }
            index--
        }
        return answer
    }
}