編程算法 - 最長上升子序列問題 代碼(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
