User:GeorgeBills/Strictly increasing sequence

From Wikipedia, the free encyclopedia

The original page is at longest increasing subsequence problem.

Contents 1 Longest common sequence version 2 Simple n2 version 3 Optimized nlogn version 4 See also 5 External links 6 References

[edit] Longest common sequence version

[edit] Simple n² version

The following is code for finding the longest strictly increasing sequence ^[1]:

int lsis( int* a, int N ) {
   int *best, *prev, i, j, max = 0;
   best = (int*) malloc ( sizeof( int ) * N );
   prev = (int*) malloc ( sizeof( int ) * N );

   for ( i = 0; i < N; i++ ) best[i] = 1, prev[i] = i;

   for ( i = 1; i < N; i++ )
      for ( j = 0; j < i; j++ )
         if ( a[i] > a[j] && best[i] < best[j] + 1 )
            best[i] = best[j] + 1, prev[i] = j; 

   for ( i = 0; i < N; i++ )
      if ( max < best[i] )
         max = best[i];

   free( best );
   free( prev );

   return max;
}

[edit] Optimized nlogn version

[edit] See also

• Dynamic programming

[edit] External links

• The problem as applied to genetics
• The Algorithm Design Manual: Longest Increasing Sequence
• The Algorithmist wiki page on the problem

[edit] References

1. ^ http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.c