Another approach for finding longest increasing subsequence

Question

I am aware that there are many algorithms for finding longest increasing subsequence, but the algorithms using DP all have this is common - they recurse/ dynimacally calculate longest subsequence "ENDING" at a particular element of the array.

I wrote a solution which resurses taking longest subsequence "starting" at a particular array, which seems to work fine too.

#include<iostream>
using namespace std;
#define boostio ios_base::sync_with_stdio(0);

int n;
int a[100000];
int t[100000] = {-1};

int lis(int i){

    if(t[i]!= -1){
        return t[i];
    }   

    if(i == n){t[i] = 1; return 1;
    }

    for (int x = i+1; x <= n ; ++x)
    {
        if(a[x] > a[i] and 1 + lis(x) > t[i]){
            t[i] = 1 + lis(x);
            //return t[i];
        }


    }

    if(t[i] != -1){
            return t[i];
        }

    t[i] = 1; return 1;



}
int main(){
    boostio;
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    fill(t, t + n+2 ,-1);

    Int m = 0;

    for (int i = 1; i <= n; ++i)
    {
        //cout << i << " " << lis(i) << endl;
        if(lis(i) >m) m= lis(i);
    }

    cout << m;

    return 0;
}

I am wondering, is this in any way worse than if we recurse on "last element" of subsequence instead of the first. They both appear to be order n square algorithms to me, so why isnt this algorithm more circulated. To me it seems more intuitive. Am I missing something?

[OT] [Please do not use `using namespace std;`](http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — NathanOliver, Feb 07 '17 at 19:49
the normal dynamic programming algorithm takes O(N log N) time. See, for example: https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms — Matt Timmermans, Feb 07 '17 at 23:22

Another approach for finding longest increasing subsequence

0 Answers0