The Longest Increasing Subsequence (LIS) problem requires us to find a subsequence t of a given sequence s, such that t satisfies two requirements:

1. Elements in t are sorted in ascending order;
2. t is as long as possible.

This problem can be solved using Dynamic Programming. We define the state P[i] to be the length of the longest increasing subsequence ends at i (with s[i] as its last element). Then the state equations are:

1. P[i] = max_{j = 0, ..., i - 1 and arr[j] < arr[i]} P[j] + 1;
2. If no such j exists, P[i] = 1.

Putting these into code using a table to store results for smaller problems and solve it in a bottom-up manner. We will have the following code.

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 int longestIncreasingSubsequence(vector
        
         & nums) { 8     vector
         
           dp(nums.size(), 1); 9     int maxlen = 0;10     for (int i = 1; i < nums.size(); i++) {11         for (int j = 0; j < i; j++) {12             if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {13                 dp[i] = dp[j] + 1;14                 maxlen = max(maxlen, dp[i]);15             }16         }17     }18     return maxlen;19 }20 21 void longestIncreasingSubsequenceTest(void) {22     int num[] = {
   10, 22, 9, 33, 21, 50, 41, 60, 80};23     vector
          
            nums(num, num + sizeof(num) / sizeof(int));24 printf("%d\n", longestIncreasingSubsequence(nums));25 }26 27 int main(void) {28 longestIncreasingSubsequenceTest();29 system("pause");30 return 0;31 }
          
         
        
       
      
     

 This program only computes the length of the LIS. If you want to print all the possible LIS, you need to modify the above program. Specifically, you may want to use backtracking to obtain all the possible LIS. My code is as follows. Welcome for any comments. Thank you!

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 /* Helper function to find all LCS. */ 8 void findAllLCSHelper(vector
        
         & nums, vector
         
          & dp, vector
          
           & seq, vector
           
            
              >& res, int maxlen, int end) { 9 if (maxlen == 0) {10 reverse(seq.begin(), seq.end());11 res.push_back(seq);12 reverse(seq.begin(), seq.end());13 return;14 }15 for (int i = end; i >= 0; i--) {16 if (dp[i] == maxlen && (seq.empty() || nums[i] < seq.back())) {17 seq.push_back(nums[i]);18 findAllLCSHelper(nums, dp, seq, res, maxlen - 1, i - 1);19 seq.pop_back();20 }21 }22 }23 24 /* Function to find all LCS. */25 vector
             
              
                > findAllLCS(vector
               
                & nums, vector
                
                 & dp, int maxlen) {26 vector
                 
                  
                    > res;27 vector
                   
                     seq;28 findAllLCSHelper(nums, dp, seq, res, maxlen, nums.size() - 1);29 return res;30 }31 32 /* Compute the length of LCS and print all of them. */33 int longestIncreasingSubsequence(vector
                    
                     & nums) {34 vector
                     
                       dp(nums.size(), 1);35 int maxlen = 0;36 for (int i = 1; i < (int)nums.size(); i++) {37 for (int j = 0; j < i; j++) {38 if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {39 dp[i] = dp[j] + 1;40 maxlen = max(maxlen, dp[i]);41 }42 }43 }44 vector
                      
                       
                         > lcss = findAllLCS(nums, dp, maxlen);45 for (int i = 0; i < (int)lcss.size(); i++) {46 for (int j = 0; j < (int)lcss[i].size(); j++)47 printf("%d ", lcss[i][j]);48 printf("\n");49 }50 return maxlen;51 }52 53 /* Test function. */54 void longestIncreasingSubsequenceTest(void) {55 int num[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};56 vector
                        
                          nums(num, num + sizeof(num) / sizeof(int));57 printf("%d\n", longestIncreasingSubsequence(nums));58 }59 60 int main(void) {61 longestIncreasingSubsequenceTest();62 system("pause");63 return 0;64 }
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

Running this program in Microsoft Visual Professional 2012 gives the following results.

0 2 6 9 11 150 4 6 9 11 150 2 6 9 13 150 4 6 9 13 156

The first four rows are the four LIS.