最长上升子序列

最长公共子序列

子串和子序列的区别:

子串是序列中连续的一串,子序列不一定连续。

思路:

dp
f[i][j];表示第一个字符串前i个字符和第二个字符串前j个字符的lcs
if(a[i]==b[j])
	f[i][j]=f[i-1][j-1];
else
	f[i][j]=max(f[i-1][j],f[i][j-1]);

时间复杂度是O(n*n),空间复杂度O(n*n);
可以使用滚动数组来减少使用空间
f[2][10000];

//字符串s1,s2是从1开始的(0号位为空格)。
int lens1 = s1.length(), lens2 = s2.length();
	for (int i = 1; i < lens1; i++)
	{
		for (int j = 1; j < lens2; j++)
		{
			if (i % 2 == 0)
			{
				if (s1[i] == s2[j])
					f[0][j] = f[1][j - 1] + 1;
				else
					f[0][j] = max(f[0][j - 1], f[1][j]);
			}
			else
			{
				if (s1[i] == s2[j])
					f[1][j] = f[0][j - 1] + 1;
				else
					f[1][j] = max(f[0][j], f[1][j - 1]);
			}
		}
	}

对于特殊情况:

若字符串序列的每个字符都不相同,则时间复杂度为O(nlogn)

假如第一个序列为

{1,3,4,6,7,4,2,9};

映射为{1,2,3,4,5,6,7,8}

对于第二个序列{3,4,5,7,2,1,}

1->1,3->2,4->3,6->4,7->5,4->6,2->7,9->8

根据第一个序列的映射情况(第一列中未出现的数字直接忽略,无影响),

对应变化为{2,3,5,7,1}

求最长上升子序列即可。

上一篇:SC Alibaba20211022 Nacos 负载均衡 rest|feign(ribbon) ----@loadbalancer


下一篇:队列实现栈以及栈实现队列