最长上升子序列(实验回顾)

今天的算法实验课是关于最长上升子序列的,总结一下。

概念

首先需要知道,子串和子序列的概念,我们以字符子串和字符子序列为例,更为形象,也能顺带着理解字符的子串和子序列:

  1. 字符子串指的是字符串中连续的n个字符,如abcdefg中,ab,cde,fg等都属于它的字串。
  2. 字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符,即可以去掉字符串中的部分字符,但不可改变其前后顺序。如abcdefg中,acdg,bdf属于它的子序列,而bac,dbfg则不是,因为它们与字符串的字符顺序不一致。

知道了这个,数值的子序列就很好明白了,即用数组成的子序列。这样的话,最长上升子序列也很容易明白了,归根结底还是子序列,然后子序列中,按照上升顺序排列的最长的就是我们最长上升子序列了。

最长上升子序列(Longest Increasing Subsequence),简称LIS,也有些情况求的是最长非降序子序列,二者区别就是序列中是否可以有相等的数。假设我们有一个序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们也可以从中得到一些上升的子序列(ai1, ai2, …, aiK),这里1<=i1<i2<…<iK<=N,但必须按照从前到后的顺序。比如,对于序列(1, 7, 3, 5, 9, 4, 8),我们就会得到一些上升的子序列,如(1,7,9), (3,4,8), (1,3,5,8)等等,而这些子序列中最长的(如子序列(1,3,5,8)),它的长度为4,因此该序列的最长上升子序列长度为4。

还有一个非常重要的问题:请大家用集合的观点来理解这些概念,子序列、公共子序列以及最长公共子序列都不唯一,但很显然,对于固定的数组,虽然LIS序列不一定唯一,但LIS的长度是唯一的。再拿我们刚刚举的栗子来讲,给出序列 ( 1, 7, 3, 5, 9, 4, 8),易得最长上升子序列长度为4,这是确定的,但序列可以为 ( 1, 3, 5, 8 ), 也可以为 ( 1, 3, 5, 9 )。

例子

输入: 2 3 6 1 7 4 10 8 9

设maxlength[i]存储以第i个元素结束的子问题最长上升子序列的长度

子问题(数组的每一位遍历) maxlength 元素值
子问题:2 maxlength[1]=1 初值
子问题:2 3 maxlength[2]= maxlength[1]+1
子问题:2 3 6 maxlength[3]= maxlength[2]+1
子问题:2 3 6 1 maxlength[4]= 1
子问题:2 3 6 1 7 maxlength[5]= maxlength[3]+1
子问题:2 3 6 1 7 4 maxlength[6]= maxlength[2]+1
子问题:2 3 6 1 7 4 10 maxlength[7]= maxlength[5]+1
子问题:2 3 6 1 7 4 10 8 maxlength[8]= maxlength[5]+1
子问题:2 3 6 1 7 4 10 8 9 maxlength[9]= maxlength[8]+1

代码

#include <iostream>
using namespace std;

void LISLength(int a[], int n) {
	int *maxlength = new int[n];	// 定义一个存储到每一位元素为止的最长子序列长度的动态数组
	*(maxlength+0) = 1;	// 设置第一个元素的值为1,及最小时为1
	int max = 1;	// 保存最大最长子序列长度,初始化为1,及最小为1

	// 遍历每一位元素,保存到每一位元素前的最长子序列长度
	for (int i = 1; i < n; i++) {
		int max_t = 0;	// 初始化每一次的最长子序列长度
		// 当前元素与之前元素的比较
		for (int j = 0; j < i; j++) {
			// 当遍历元素大于其前面的此元素,且大于遍历过的最长子序列长度时
			if (a[i] > a[j] && *(maxlength+j) > max_t) {
				max_t = *(maxlength + j);	// 更新最长子序列长度
				*(maxlength + i) = *(maxlength + j) + 1;	// 到该遍历元素的最长子序列长度
			}
			// 当遍历元素小于前面所有的元素时,设置到该遍历元素的最长子序列长度 为 1
			else if(max_t == 0 && j == i -1)
			{
				*(maxlength + i) = 1;
			}
		}
		// 更新最长子序列长度值
		if (*(maxlength + i) > max)
			max = *(maxlength + i);
	}

	cout << "最长子序列长度:" << max << endl;

	delete[] maxlength;	// 销毁动态数组
}

int main() {
	int n = 0;
	cout << "请输入数组大小:" << endl;
	cin >> n;
	int* arr = new int[n];	// 定义动态数组
	cout << "请输入数据:" << endl;
	// 输入数组数据
	for (int i = 0; i < n; i++) {
		cin >> *(arr+i);
	}

	LISLength(arr, n);

	delete[] arr;	// 销毁动态数组

	return 0;
}

效果

image-20201208225438176

原文地址:https://www.cnblogs.com/Liwker/p/14106179.html