程式設計算法 - 最長上升子序列問題 代碼(C)

最長上升子序列問題 代碼(C)

本文位址: http://blog.csdn.net/caroline_wendy

題目: 有一個長為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 <stdio.h>

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

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>
#include <memory.h>
#include <limits.h>

#include <algorithm>

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<n; ++i) {
			dp[i] = 1;
			for (int j=0; j<i; ++j) {
				if (a[j]<a[i]){
					dp[i] = max(dp[i], dp[j]+1);
				}
			}
			res = max(res, dp[i]);
		}
		printf("result = %d\n", res);
	}

	void solve2() {
		fill(dp, dp+n, INF);
		for (int i=0; i<n; i++) {
			*lower_bound(dp, dp+n, a[i]) = a[i];
		}
		printf("result = %d\n", lower_bound(dp, dp+n, INF)-dp);
	}
};

int main(void)
{
	Program iP;
	iP.solve2();

	return 0;
}

           

輸出:

result = 3