编程算法 - 最长上升子序列问题 代码(C)

最长上升子序列问题 代码(C)

?

?

题目: 有一个长为n的数列a. 请求出这个序列中最长上升子序列的长度. 最长上升子序列的数字之间可以有间隔.

即最长上升子序列(LIS, Longest Increasing Subsequence), 例如: n=5, a={4,2,3,1,5}, result=3(2,3,5).

?

使用动态规划求解(DP).

方法1: 依次求出每个数字之前的最长上升子序列, 时间复杂度O(n^2).

方法2: 求取针对最末位的元素的最长子序列, 使用较小的元素更新数组, 应用二分搜索查找元素, 时间复杂度(nlogn).

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; class Program { static const int MAX_N = 100; const int INF = INT_MAX>>2; int n = 5; int a[MAX_N] = {4, 2, 3, 1, 5}; int dp[MAX_N]; public: void solve() { int res = 0; for (int i=0; i
        
        输出:
        
?
        
?
        
result = 3
 
        
 
        
 
        
?
 
        
?
 
        
?
 
        
?
 
        
 
        
?
 
        
?