(Leetcode 300) LIS (V.IMPORTANT) INITIAL ANALYSIS FOR JUMP DP STATE REDUCTION WITH LOOP & BS

class Solution {
public:
    int getLIS(int level, vector<int> &nums, vector<int> &memo){
        if(level >= nums.size()){
            return 0;
        }
        //ALWAYS INCLUDE THE ELEMENT OF THE CURRENT LEVEL (INCLUDING GIVES THE LONGEST CHAIN, by increasing length by 1 always)
        //element itself is a VALID SUBSEQUENCE OF LENGTH 1 (VALID = PROPERTY HOLDS)

        //******IMPORTANT
        //THIS length = 1, is for the case where the LOOP NEVER RUNS(no j > i, where nums[j] > nums[i]), IF THE LOOP NEVER RUNS length = 1
        // Length should 1, if loop never runs, as that makes sure that there is no other VALID LEVEL TO JUMP TO,
        //but the CURRENT LEVEL ELEMENT MUST BE INCLUDED, no matter if it calls forward or not, as it is VALID LEVEL
        //(we must have jumped to this level from some previous level) and WE ARE INCLUDING EVERY LEVEL's element we jump to
        //USE BOOL flag for more clarity.
        //bool loopRan = false;
        //if the flag becomes true; if loop runs make this true, which ensures that this level must have called forward somewhere,
        //and the length will  be correctly counted by doing 1 + getLIS().
        //But if flag is false, then it is LAST VALID LEVEL, and it should be added to the subsequence explicitly by returning 1.
        /*
        So
        bool loopRan = false;
        loop(){
            loopRan = true;
        }
        return memo[level] = loopRan ? length : 1;
        */
        int length = 1;
        //include
        //directly jump to next valid level (some level j, where nums[j] > nums[i], j > i)
        //it reduces the state memo(level, lastIdx) to memo(level)

        //we needed lastIdx to take decision if current element can be included or not
        //But with the help of LOOP we directly JUMP to next VALID INDEX
        //IT IS LIKE THAT JUMP DP, where we directly jump to JUST NEXT VALID INDEX with the help of Binary Search
        //Here we CAN'T use Binary Search as the array is NOT in SORTED ORDER and we CAN'T SORT the array, as we need to find Longest Increasing SUBSEQUENCE
        //SUBSEQUENCE IS ORDER DEPENDENT, ELEMENT MUST BE PICKED IN THE SAME ORDER AS THEY APPEAR IN THE ARRAY
        //SUBSET IS ORDER INDEPENDENT, ELEMENT CAN BE PICKED IN ANY ORDER IRRESPECTIVE OF THEIR ORDER IN THE ARRAY
        //So we want to find SUBSEQUENCE, so we can't sort, BUT we can LOOP INSTEAD.
        // WE USED BINARY SEARCH TO DIRECTLY JUMP TO THE NEXT VALID LEVEL, which REDUCES THE NEED FOR lastIdx, as we are ALWAYS ON A VALID LEVEL
        //IF you can SORT THE ARRAY, USE BINARY SEARCH TO DO THE JUMP(log(n)) BUT if you CAN'T SORT the array, USE LOOP(O(n))
        //With LOOP as with BINARY SEARCH, WE GUARANTEE THAT WE ONLY EXPLORE VALID LEVELS ONLY, so no need to check if current element can be included
        // YOU WILL ALWAYS HAVE BOTH OPTIONS AS VALID (at every level, you can always INCLUDE and EXCLUDE)
        // Earlier we always have to check if can INCLUDE the CURRENT LEVEL ELEMENT with the help of conditional (nums[level] > nums[lastIdx])
        //Now no CONDITIONAL is needed, as we can explore both the options at EVERY LEVEL we go to, as we are only jumping to a level with both options enabled.
        //NO conditional was being used to explore the option to exclude, as excluding the CURRENT LEVEL ELEMENT from the SUBSEQUENCE doesn't violate the property of subsequence
        //As we are going to exclude the element from the subsequence, it won't violate ...
        //CONDITIONAL is only NEEDED when we are going to INCLUDE the CURRENT LEVEL ELEMENT into the subsequence, because the element that is going to be included in the subsequence
        //should be larger than the element that was previously included in the subsequence.
        //But while exploring the options, we do level + 1 BLINDLY, and check at every LEVEL, whether to explore the include option or not.
        //We only explore INCLUDE option, when adding the element doesn't violate the property of subset(a1 < a2 < a3)
        // BUT with the help of LOOP(JUST AS WITH BINARY SEARCH), we make SURE to not explore INVALID LEVELS.
        //WE ONLY MOVE TO THOSE LEVELS, WHICH HAVE BOTH OPTIONS AS VALID, so we can explore BOTH. So whatever level we go to, we can exclude the element(doesn't violate the property anyway)
        // and we can also EXPLORE the OPTION to include the element WITHTOUT NEEDING TO USE A CONDITIONAL(nums[j] > nums[i], j > i), as WITH THE HELP OF THE LOOP,
        // WE ONLY GO TO THOSE LEVELS at which the PROPERTY OF THE SUBSEQUENCE HOLDS.

        //include
        //directly jump to next valid level where property HOLDS (some level j, where nums[j] > nums[i], j > i)
        //AS property is always going to HOLD no matter what options we explore as all are VALID, we don't need to USE CONDITIONAL
        //REDUCES THE need of another parameter such as lastIdx
        //REMEMBER
        //IF ASKED FOR SUBSEQUENECE(ORDER DEPENDEDENT), ORDER OF ORIGINAL ARRAY CAN'T BE CHANGED, CAN'T BE SORTED, SO NO BINARY SEARCH, USE LOOP INSTEAD
        //IF ASKED FOR SUBSET(ORDER INDEPENDENT), ORDER OF ORIGINAL ARRAY CAN BE CHANGED TO FORM THE BEST ANSWER, CAN BE SORTED, SO BINARY SEARCH INSTEAD OF LOOP TO OPTIMISE
        for(int j = level + 1; j < nums.size(); j++){
            if(nums[j] > nums[level]){
                length = max(length, 1 + getLIS(j, nums, memo));
            }
        }
        //Exclude
        //*******IMPORTANT
        //EXPLORE THE OPTION TO EXCLUDE explicitly to HANDLE the CASE from where the LIS will START FROM, TO CHOOSE WHAT IS THE FIRST ELEMENT
        //AFTER THE FIRST ELEMENT IS CHOSEN at some level i, we ALWAYS JUMP TO A VALID LEVEL WHERE PROPERTY WILL ALWAYS HOLD (nums[j] > nums[i], j > i) with
        // the help of LOOP or BS, depending if the array is SORTED OR NOT(SUBSEQUENCE OR SUBSET)
        //BUT for the first element, We start from level 0.
        // As per our definition we always are on a VALID LEVEL, which makes level 0 always VALID(certainly not true), and we INCLUDE THIS ELEMENT as our STARTING POINT always.
        // We explore every VALID OPTION ONCE THE FIRST ELEMENT IS CHOSEN WITH THE HELP OF LOOP or BS, but what about the FIRST ELEMENT ITSELF.
        // USING FOR LOOP GUARANTEES WE LAND ON A VALID LEVEL (where both options are valid), but the FIRST RECURSIVE CALL start from 0, which by definition
        // that we only EXPLORE VALID LEVELS, makes an FALSE assumption that LEVEL 0 is always valid, which MAKES each of our LIS that is formed
        // start from level 0, MAKING level 0/index 0 element a STARTING POINT OF EVERY LIS THAT WE EVER FORM, which is not TRUE, as our LIS can literally start from anywhere.
        //It is just we decided to start from level 0, to start recursion, makes it VALID BY ACCIDENT, and we choose 0th index element
        //as our FIRST ELEMENT OF ALL THE POSSIBLE INCREASING SUBSEQUENCES THAT WE FORM

        //RECTIFY IT BY GIVING FREEDOM TO CHOOSE THE FIRST ELEMENT OF THE EVERY LIS THAT WE FORM, i.e. it  can START FROM ANY INDEX
        //BASICALLY GIVE AN OPTION TO EXCLUDE IF WE CHOOSE OUR FIRST ELEMENT.

        //IT CAN BE DONE SIMPLY APPLYING THE SAME FOR LOOP TO THE FIRST CALL IN THE SERIES ITSELF
        //BUT AS IT IS THE FIRST ELEMENT OF THE SEQUENCE(subsequence, subset) no need to compare, as a subsequence of length 1 is always a VALID LIS
        //CURRENTLY WE START FROM 0, BUT WE COULD HAVE STARTED FROM ANYWHERE ON THE ARRAY
        //LOOPING ON THE FIRST RECURSIVE CALL, gives every element of the array to be the STARTING POINT of LIS.
        return length;
    }
    //*********IMPORTANT
    //AS WE ARE USING LOOP, we only EXPLORE VALID OPTIONS. We have both INCLUDE AND EXCLUDE. BUT WHY EXCLUDE THE CURRENT ELEMENT explicitly??????
    //INCLUDING THE CURRENT ELEMENT WILL ALWAYS INCREASE THE SIZE OF LIS by 1 and we are always on a VALID LEVEL ALWAYS(where we can explore both), which guarantees that we can explore INCLUDE
    //without any hesitation that if it would make the subsequence INVALID.
    //EXCLUDING THE CURRENT ELEMENT WILL HAPPEN WITH THE FOR LOOP IMPLICITLY ANYWAYS, no NEED to exclude explicitly.
    // WE ONLY EXPLORE LEVELS WITH BOTH OPTIONS AVAILABLE, SO WE CHOOSE WHAT GIVES US THE BEST ANSWER EVERYTIME!!!! & Including always increases
    //LENGTH, so WE ALWAYS INCLUDE THE ELEMENT WE LAND ONTO!!!!!!!!!!
    int lengthOfLIS(vector<int>& nums) {
        vector<int> memo(nums.size(), -1);
        //as we are on this LEVEL, we are going to include this ELEMENT (AS on every level we will always include, because include is the BEST OPTION)
        int length = 1;
        //IMPORTANT******** Each 'i' is a VALID STARTING INDEX FOR LIS, as the first element in LIS is always VALID(increasing(nothing to compare it to) and a valid subsequence of array)
        for(int i = 0; i < nums.size(); i++){
            //no need to add 1 here (1 + getLIS()), we already have done length = 1, which makes sure that we included the element
           length = max(length, getLIS(i, nums, memo));
        }
        return length;
    }
};