This video explains a very important dynamic programming problem which is a variant of longest increasing subsequence (LIS).The problem is to find the largest divisible subset in such a way that all the elements in the subset are pairwise divisible.We need to return all the subset elements irrespective of their order.I have explained how to apply recursion and backtracking to this problem and i have also shown why recursion will fail.I have shown how this problem can be reduced to longest increasing subsequence problem (LIS).I have shown all the steps clearly with proper examples and at the end, i have shown the code walk through.CODE LINK is present below as usual.For the DAY-13 leetcode problem "Largest Divisible Subset", SORTING is essential and it cannot be solved without sorting because a number should have all the divisors to its left to be absolutely sure about including it in the same subset.This ASC order is important for decision making. Consider [9,18,6]. Here, if we are at 6 then we will compare with 18 and it will divide and so we will try to include in the SET with 18. But 18 is already in a SET with 9 which is [9,18] and therefore this will give wrong answer. If we first sort it to [6,9,18], then this will always give you correct answer.So, please ignore what i said about solving without sorting. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.co...
SIMILAR PROBLEMs:-
Longest Increasing Subsequence (LIS): • Longest increasing sub...
Longest common subsequence (LCS): • Longest common subsequ...
Longest common substring: • Longest common substri...
Longest palindromic substring (LPS): • Longest palindromic su...
Негізгі бет Largest Divisible Subset | Dynamic programming | Leetcode
No video
Пікірлер: 152