Day 102.md

Day 102

Link: https://x.com/kom_senapati/status/1778748798178881981

Approach

• Created a LIS vector with initial value 1
• Traversed the given vector in reverse order and updated the max LIS starting from that sequence by using another loop
• Atlast returned the maximum value in vector LIS

Code

int Solution::lis(const vector<int> &A) {
    if(A.size() == 0){
        return 0;
    }
    
    vector<int> LIS(A.size(), 1);
    
    for(int i = A.size()-2; i > -1; i--){
        for(int j = i+1; j < A.size(); j++){
            if (A[i] < A[j]){
                LIS[i] = max(LIS[i], 1+LIS[j]);
            }
        }
    }
    
    return *max_element(LIS.begin(), LIS.end());
}