Fastest Implementation of Longest Increasing Subsequence problem

LIS.cpp

//
// Created by Harsh Vardhan Kumar on 28-02-2018.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <deque>
#include <sstream>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>

#define INT_MAX std::numeric_limits<int>::max()
#define INT_MIN std::numeric_limits<int>::min()
#define LONG_MAX std::numeric_limits<long long>::max()
#define LONG_MIN std::numeric_limits<long long>::min()

using namespace std ;
vector<string> split(string & s) {
    vector<string> result ;
    s+='.' ;
    string s1 ;
    for(char c : s) {
        if(c!='.') {
            s1+=c ;
        }
        else {
            result.push_back(s1);
            s1 = "" ;
        }
    }
    return result ;
}

int main() {
    cout<<"Enter the number of numbers"<<endl ;
    int n ; cin>>n ;
    vector<int> numbers(n) ;
    for(int i = 0 ; i<n ; i++) {
        cin>>numbers[i] ;
    }
    unordered_map<string, pair<int,int> > arrays_sequences ; // we store the currently found LIS till ith index as the string and to help us
                                                  // find out whether the current number will be added to this LIS or not, we need the
                                                  // last number of the LIS. We store this last number as the first parameter of the second parameter in the map.
                                                  // the second parameter of the second parameter will store the no. of elements in the string to determine the ans.
                                                    // we use the unordered_map and the string to reduce the amount of the memory used to store the no. of partial solutions.
    // bottom up approach. initializing the base case.
    arrays_sequences[to_string(numbers[0])] = make_pair(numbers[0],1) ;
    string ans = to_string(numbers[0]); int noOFElementsInAnswer = 1; // helpful to determine the no. of elements in the ans string. If we do not store this value, then we will have to determine the total no. of elements present in the ans using a O(n) loop and thus the total running time would be O(n^3)

    for(int i = 0 ; i<n ; i++) {
        string localBest = to_string(numbers[i]); int noOFElementsInLocalAnswer = 1 ;
        for(pair<string, pair<int,int> > vs : arrays_sequences) {
            string v = vs.first ;
            if( numbers[i]>vs.second.first) {
                string v1 = v+"."+to_string(numbers[i]) ;
                if(vs.second.second+1 >= noOFElementsInLocalAnswer) {
                    localBest = v1;
                    noOFElementsInLocalAnswer = vs.second.second+1 ;
                }
                if(vs.second.second+1>=noOFElementsInAnswer) {
                    ans = v1;
                    noOFElementsInAnswer = vs.second.second+1 ;
                }
            }
        }
        arrays_sequences.insert(make_pair(localBest, make_pair(numbers[i], noOFElementsInLocalAnswer))) ;
    }

    cout<<"The Longest Increasing Subsequence is "<<endl ;
    for(string a : split(ans)) cout<<a<<" "; cout<<endl ;
}