最长上升子序列 Longest Increasing Subsequence 输出其中一个序

#include <iostream>
#include <stack>
using namespace std;
//dp[i] 表示以A[0~i]的最长上升子序列的长度
//dp[0] = 1 当i=0
//dp[i] = 1 + max{dp[j], 0<j<i并且A[j]<A[i]} 当0<i<=n
//A[0~i]的最长子序列可由A[0~i-1]的最长子序列求得
//时间复杂度O(n^2)
int lis_dp(int seq[], int n) {
	int *dp = new int[n];
	int *pre = new int[n];
	for (int i = 0; i < n; ++i) {
		dp[i] = 0;
		pre[i] = -1;
	}
	dp[0] = 1;
	pre[0] = -1;
	for (int i = 1; i < n; ++i) {
		int max = 0;
		for (int j = 0; j < i; ++j) {
			if (seq[j] < seq[i] && max < dp[j]) {
				//找到A[0~i-1]中的最长序列
					max = dp[j]; 
					pre[i] = j; //seq[i]的前驱元素所在下标
			}
		}
		dp[i] = 1 + max;
	}
	
	int max = 0;
	int i_max = 0;
	for (int i = 0; i < n; ++i) {
		if (max < dp[i]) {
			max = dp[i];
			i_max = i;
		}
	}	
	
	stack<int> s;
	int k = i_max;
	while (k >= 0) {
		s.push(seq[k]);
		k = pre[k];
	}
	while (!s.empty()) {
		cout << s.top() << "|";
		s.pop();
	}
	cout << endl;
	delete[] dp;
	delete[] pre;
	return max;
}

//找到一个j满足 array[j] < key <= array[j+1] 区间二分搜索
//返回j+1
int binary_search(int array[], int key, int low, int high) {
	while (low <= high) {
		int mid = (low + high) / 2;
		if (array[mid] < key && key <= array[mid+1]) { 
			//由于array严格单调递增，又key >= array[high]
			//mid+1不会溢出，想想为什么
			return mid + 1;
		}
		if (array[mid] < key) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
}

int lis_greedy(int seq[], int n) {
	int top = 0;
	int* stack = new int[n];
	for (int i = 0; i < n; ++i) {
		stack[i] = 0;
	}
	stack[top] = seq[0];
	for (int i = 0; i < n; ++i) {
		if (seq[i] > stack[top]) {
			//如果seq[i]大于栈顶元素，则入栈
			stack[++top] = seq[i];
		} else {
			//从栈底开始，找到第一个>=seq[i]的元素所在位置
			int replace = binary_search(stack, seq[i], 0, top);
			stack[replace] = seq[i];
		}
	}
	for (int i = 0; i <= top; i++) {
		cout << stack[i] << "|";
	}
	cout << endl;
	delete[] stack;
	return top + 1;
}

int main(int argc, char* argv[]) {
	//int arr[] = {6,3,7,11,12,10,1,13,8,5,4,15,14,9,2};
	int arr[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
	int len = sizeof(arr) / sizeof(int);
	cout << len << endl;
	cout << lis_dp(arr, len) << endl;
	cout << lis_greedy(arr, len) << endl;
	return 0;
}
/* 第一组测试数据
15
6|7|11|12|13|15|
6
1|2|8|9|13|14|
6
*/