Longest Divisible Subset(length) O(N^2) time and O(N) space COMMENTS NEED UPDATION

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


//APPROACH 1 T.C. O(N^2), SPACE - O(N^2)
int getMaxChain(int level, int lastIdx, vector<int> &v, vector<vector<int> > &memo1){
    if(level >= v.size()){
        return 0;
    }
    if(lastIdx != -1 && memo1[level][lastIdx] != -1){
        return memo1[level][lastIdx];
    }
    int lengthInc = 0, lengthExc = 0;
    // include current level only when the lastIdx element divides level or the element being included is the FIRST element of the subset
    if(lastIdx == -1 || v[level] % v[lastIdx] == 0){
        lengthInc = 1 + getMaxChain(level + 1, level, v, memo1);
    }
    //exclude, no condition needed on exclusion, as it doesn't change the subset, so exploring this option won't violate the property of subset being formed
    lengthExc = getMaxChain(level + 1, lastIdx, v, memo1);
    if(lastIdx != -1){
        memo1[level][lastIdx] = max(lengthInc, lengthExc);
    }
    return max(lengthInc, lengthExc);
}

//APPROACH 2 T.C. O(N^2) SPACE - O(N^2) [optimal]
//USE BINARY SEARCH (Binary search can't be used as the predicate logic doesn't mean anything when used to disregard a half)
// BINARY SEARCH can only be used in an increasing range. We already SORTED the array to guarantee the maximum length of SUBSET.
//BINARY SEARCH reduces the T.C and S.C by removing redundancy in the MEMO KEY
// previously we had memo(level, lastIdx) which will be reduced to memo(level).... WHY???
//What lastIdx was being tracked? TO DECIDE WHETHER THE CURRENT ELEMENT CAN BE INCLUDED IN THE SET OR NOT(satify property)
// Why this was necessary? TO FORM ONLY A VALID SEQUENCE/SUBSET BY ONLY PICKING THOSE ELEMENTS THAT FOLLOW PROPERTY
//(process EVERY element in the array, use CONDITIONAL to avoid INVALIDS)
// Essentially we move to level + 1, when we explore, that mostly takes us to some INVALID levels, where we need to USE some CONDITIONAL to AVOID EXPLORING OPTIONS that will result in a faulty subset.
// because we are using INDEX BASED TRAVERSAL, and we EXPLORE OPTIONS at EACH LEVEL(level) and MOVE TO NEXT LEVEL(level + 1), NO MATTER which OPTION we explore. (we are doing BLIND RECURSION(incrementing level by 1) with a CONDITIONAL to guarantee generation of VALID SUBSETS. GOOD APPROACH but we can do better.

// WHAT BINARY SEARCH HELPS US WITH => *********IMPORTANT
// RECURSE SMARTLY, for EVERY OPTION EXPLORED, JUMP DIRECTLY TO THE NEXT VALID INDEX, SKIP THE IN BETWEEN INVALIDS.

//We won't do BLIND RECURISON anymore, We won't INCREMENT LEVEL BY 1 for EVERY OPTION that we EXPLORE at any level
// We will do SMART RECURSIION. INCREMENT level by SOMETHING, that DIRECTLY takes us to NEXT VALID INDEX.
// WHAT THIS WILL DO? -> from some VALID LEVEL we are on, JUMP TO SOME LEVEL DIRECTLY, that is the NEXT VALID.
// What we were doing earlier?
// from some LEVEL, EXPLORE VALID OPTIONS(use conditionals), JUMP to the NEXT LEVEL that might be INVALID/VALID(because we do blind increment by 1 to generate all possible combination and choose the BEST)


int getMaxChainWithJUMPS(int level, vector<int> &v, vector<int> &memo2){
    if(level >= v.size()){
        return 0;
    }
    if(memo2[level] != -1){
        return memo2[level];
    }
    //****IMPORTANT size of subset would atleast be 1(that element itself/ a1 itself, property self satisfied)
    //don't return 0, as the element itself is valid subset following the property
    int length = 0;
    bool flag = false;

    //include only if it doesn't violate the property of subset
    //explore options then JUMP STRAIGHT to the NEXT VALID level
    //NEXT VALID ELEMENT would be any element in range[level + 1, v.size() - 1] that follows v[i] % v[level], i > level
   for(int i = level + 1; i < v.size(); i++){
       if(v[i] % v[level] == 0){
           flag = true;
           length = max(length, 1 + getMaxChainWithJUMPS(i, v, memo2));
       }

   }

   return memo2[level] = flag == true ? length : length + 1;
}

int main() {
    // your code goes here
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    // IMPORTANT We need to find the chain of maximum length using a SUBSET of elements and not SUBSEQUENCE

    //SUBSEQUENCE is where ORDER matters, and so you can't change the original sequence of elements, eg LIS, so no sorting
    //SUBSET is where you pick elements no matter the ORDER. SUBSET is basically some COMBINATION of elements NOT necessarily CHOSEN/PICKED in ORDER as they appear in the original array(subset sum question, mask).

    // So you can pick element in any order, put them together in a sequence where it will maximise the length.
    // the property {a1|a2|a3} where a1 divides a2, and a2 divides a3
    //AN IMPORTANT OBSERVATION - to suffice the above rule, a1 < a2 < a3

    // So to get the maximum length we need to make sure that elements are in ascending order, GUARANTEEING the chance to find the LONGEST SEQUENCE.
    sort(v.begin(), v.end());

    //memo table APPROACH 1 = memo(level, lasIdx) T.C. AND SPACE = O(N^2)
    vector<vector<int> > memo1(n, vector<int>(n, -1));
    // cout << getMaxChain(0, -1, v, memo1) << '\n';

    //memo table APPROACH 2 = memo(level) T.C ~ O(N^2) AND SPACE = O(N)
    int length = 0;
    vector<int> memo2(n, -1);
    //loop through all the elements as our subset can start with any element not necessarily the first one.
    //give every element the chance to be the first element in the subset
    //As implicit recursion takes care of only calling/moving to valid levels by using the LOOP, but the initial/original recursive call from main(that I called, was without validation), if called without loop, would always start with 0th index (general index based traversal), and we start recursion with 0th element. IN OUR RECURSIVE DEFINITION, AS WE ONLY EXPLORE VALID LEVELS,SO IF A STATE IS REACHED IN RECURSION, RECURSION ASSUMES THAT IT IS A VALID LEVEL(means the last element included will always divide the current element), AND WE ARE GOING TO INCLUDE IT as we have reached the level.

    //******* IMPORTANT
    //SO IF A STATE IS REACHED, WE ARE ALWAYS GOING TO INCLUDE THE ELMENT.
    //WE ALWAYS REACH A VALID LEVEL(where all the options are valid), so here include and exclude both are valid.
    //BUT INCLUDE ALWAYS INCREMENTS THE LENGTH BY 1 and EXCLUDE DOESN'T, SO WE ONLY EXPLORE THE INCLUDE OPTIONS AT EVERY VALID LEVEL WE JUMP, because that is the best option to explore
    //For the 2nd element in subset, or the 3rd element included in subset, we would have reached that level where we are including the 2nd element or 3rd element, only when that level element is divisible by the previous level element. So we would have called to the level where 2nd element is going to be included from the level where 1st element was included by checking prior to making the call, that if the level we are moving to, where we are going to include/find the 2nd element of subset is divisble by 1st element of the subset at current level, i.e.
    /*
    for(i in range(level + 1 : v.size() - 1)){
        if(v[i] % v[level] == 0){
            recurse to level i.
        }
    }

    BUT the first element that is going to included in the subset, does not need to be divisible by anything, because it is the first element, and there is no prior element to it. SO once a level is reached, we are bound to include that element. But the recursive call
    */
    for(int i = 0; i < n; i++){
        length = max(length, getMaxChainWithJUMPS(i, v, memo2));
    }
    cout << length << '\n';
}