Longest increasing subsequence

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

algorithm: use an array for each element’s longest subsequence. initial value is 1, if any previous number A that  is smaller and A’s LIS is bigger, then the value +1. The longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.

class LongestIncreasingSubsequence{

public int getLongest(int[] a){

int[] lth = new int[a.length];

lth[0]=1;

for(int i=0; i<a.length;i++){

lth[i] = 1;

for(int j=0; j<i;j++){

if(a[i]>a[j] && lth[i] <= lth[j]){

lth[i] = lth[j] + 1

}

}

}

int max = 0

for(int i=0; i<lth.length; i++){

if(lth[i] > max)

max=lth[i];

}

return max;

}

}

Advertisements

3 comments

  1. czy zbasz o swoją flagę · April 12, 2013

    Nice blog here! Also your website loads up very fast!
    What host are you using? Can I get your affiliate link to your host?
    I wish my site loaded up as quickly as yours lol

  2. reklama dźwignią handlu · May 1, 2013

    Design, Tech and Internet post extremely fascinating therefore I’ve included our track-back for
    it on my own webpage, continue the great job:
    )
    Excellent post, you’ve got pointed out some wonderful details , I too conceive this s a quite wonderful site.
    Would really like to perpetually get updated excellent weblog ! .
    I like this post, enjoyed this one thanks for posting .
    I went more than this web website and I believe you might have a lot of wonderful data, saved to fav (:.
    As soon as I located this internet internet site I went on reddit to share some with the love with them.
    Regards for this terrific post, I am glad I discovered this website on yahoo.
    Woh I love your posts , bookmarked ! My wife and i take concern along with your last point.
    What is excellent respecting is dealing with instead of depending on.
    I’m not that considerably of a internet reader to be honest but your web sites truly nice, keep it up! I’ll go ahead and bookmark your web site to come back later. All the best
    A properly written write-up, I just passed this onto a workfellow who was doing somewhat analysis on this. And he indeed purchased me dinner because I discovered it for him…. .. therefore let me reword that: Thnkx for the treat nonetheless yeah Thnkx for spending the time to speak about this, I feel strongly concerning it and really like reading far more on this topic. If doable, as you gain expertise, would you mind updating your weblog with a lot more details? it really is extraordinarily helpful on behalf of me. massive thumb up for this weblog
    An attention-grabbing dialogue is value comment. I’m certain that its greater to write on this subject, towards the often be a taboo topic but typically persons are not sufficient to speak on such topics. To an additional location. Cheers
    Thanks a great deal for being our mentor on this niche. I enjoyed your current write-up extremely considerably and most of all cherished how you genuinely handled the aspect I considered to be controversial. You’re always quite kind to readers much like me and let me in my everyday living.
    Thank you.
    Remarkably! It really is as if you read my mind!

    A person appear to know therefore considerably relating to this, just like
    you authored the book inside it or something. I feel that you can do with a couple of images to
    drive the content material residence a bit, on top
    of that, this genuinely is fantastic weblog. The outstanding study.
    I will definitely review again.
    Wow! This could be 1 specific of the most helpful blogs We’ve ever arrive across
    on this topic. Really Wonderful. I’m also an
    expert in this subject therefore I can realize your hard work.

    There is noticeably a whole lot to know about this.
    I believe you made some good points in capabilities also.

    Greetings! Quick question that’s completely off
    topic. Do you know how to make your website mobile friendly?

    My weblog looks weird when viewing from my iphone.
    I’m trying to find a template or plugin that may possibly
    be able to fix this difficulty. Should you have any recommendations, please share.

    Appreciate it!
    As a Newbie, I am always exploring online for articles that can
    be of assistance to me. Thank you
    I must test with you here. Which is not 1 thing I normally do!
    I enjoy studying a submit that will make folks believe.
    Also, thanks for allowing me to comment!
    Howdy! Do you know if they make any plugins to
    safeguard against hackers? I’m kinda paranoid about losing everything I’ve worked hard on.

    Any suggestions?
    Hi! I’m reading your web site Luix Free of charge Premium WordPress Theme Download

  3. play online backgammon · June 20, 2014

    I don’t know whether it’s just me or if everyone else
    encountering issues with your blog. It appears like some of
    the text within your posts are running off the screen. Can somebody else
    please comment and let me know if this is happening to them as well?
    This could be a problem with my browser because I’ve had this happen before.

    Appreciate it

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s