[Java] ✨✨✨ (Explained!) Dynamic Programming - finding together optimized way!
Intuition\nLet\'s detect some findings:\n1) We have 3 numbers: a, b, c, where a < b < c. If c % b == 0 && b % a == 0, then c % a == 0 (Exercise: prove it!).\nIt
# Intuition\nLet\'s detect some findings:\n1) We have 3 numbers: a, b, c, where a < b < c. If c % b == 0 && b % a == 0, then c % a == 0 (Exercise: prove it!).\nIt means, each smaller number can "inherit" lists of bigger numbers, if those bigger numbers give 0 remainder after division to the smaller number.\n2) We can store the longest chains of numbers (satisying the description) starting from the biggest one. For this we can first sort the array, and then start from n-1 down to 0, and actively using finding #1.\n\n# Approach\n1) Sort the array nums ascending. n is the size of nums.\n2) Initialize dp array of **lists** of size n. Assign list of just single (n-1)-th element to dp[n-1] (as the biggest element can form the chain only with itself).\n3) For each index i from (n-2) to 0 - navigate through j from (i + 1) to (n-1) and check 2 conditions:\n3.1) nums[j] % nums[i] == 0.\n3.2) dp[j].size() > maximum size of the list found so far.\nIf both conditions match - track index j as the source of the longest list forming sequence with i-th element.\n4) If dp[i] size is more than maximum chain size found so far - update the maximum chain (list).\n5) Return maximum list.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n^2)$$\n\n# Code\n```\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        int n = nums.length;\n        Arrays.sort(nums);\n        ArrayList<Integer>[] dp = (ArrayList<Integer>[]) new ArrayList[n];\n        for (int i = 0; i < n; i++) {\n            dp[i] = new ArrayList<>();\n        }\n        dp[n-1].add(nums[n-1]);\n        List<Integer> longestList = dp[n-1];\n        for (int i = n-2; i >= 0; i--) {\n            int maxIndex = n;\n            for (int j = i + 1; j < n; j++) {\n                if (nums[j] % nums[i] == 0 && (maxIndex == n || dp[j].size() > dp[maxIndex].size()))  {\n                    maxIndex = j;\n                }\n            }\n            dp[i] = new ArrayList<>();\n            dp[i].add(nums[i]);\n            if (maxIndex != n) {\n                for (int dpNum: dp[maxIndex]) {\n                    dp[i].add(dpNum);\n                }\n            }\n            if (longestList.size() < dp[i].size()) {\n                longestList = dp[i];\n            }\n        }\n        return longestList;\n    }\n}\n```\n\n# Space optimized O(n) solution \nWe don\'t really need to keep track of the lists themselves - for each i-th element we can just store 2 values:\n1) Size of the longest list i-th element is forming;\n2) Next index j of the element in nums that forms the list with i-th element, i.e. such j where the list for nums[i] would look like:\n[i, j, .....]\n\nIn the end we can just start from the index forming the longest list (we can keep track of this index as we go) and add elements as long as we don\'t reach n-th (non-existing) element.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n```\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        int n = nums.length;\n        Arrays.sort(nums);\n        int[][] dp = new int[n][2];\n        dp[n-1][0] = n;\n        dp[n-1][1] = 1;\n        int longestListSize = 1;\n        int longestListSizeIndex = n-1;\n        for (int i = n-2; i >= 0; i--) {\n            int maxIndex = n;\n            for (int j = i + 1; j < n; j++) {\n                if (nums[j] % nums[i] == 0 && (maxIndex == n || dp[j][1] > dp[maxIndex][1]))  {\n                    maxIndex = j;\n                }\n            }\n            dp[i][0] = maxIndex;\n            dp[i][1] = (maxIndex == n ? 0 : dp[maxIndex][1]) + 1;\n            if (longestListSize < dp[i][1]) {\n                longestListSize = dp[i][1];\n                longestListSizeIndex = i;\n            }\n        }\n        List<Integer> res = new ArrayList<>();\n        int i = longestListSizeIndex;\n        while (i < n) {\n            res.add(nums[i]);\n            i = dp[i][0];\n        }\n        return res;\n    }\n}\n```
['Java']