“最大连续子序列和”、“最大递增子序列”、“最大公共子序列”、“最长公共子串”问题总结【持续更新ing】_最长连续子序列和最大

一、最大连续子序列和（最大子序列）

leetcode链接：https://leetcode.com/problems/maximum-subarray/

最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2}，它的和是8,达到最大；而 {5,-6,4,2}的最大子序列是{4,2}，它的和是6。

解法①：暴力解法

一般情况下，先从暴力解分析，然后再进行一步步的优化。

求子序列和，那么我们要知道子序列的首尾位置，然后计算首尾之间的序列和。用2个for循环可以枚举所有子序列的首尾位置。 然后用一个for循环求解序列和。这里时间复杂度太高，O(n^3).

复杂度分析

• 时间复杂度： O(n^3)
• 空间复杂度： O(1)

解法②：前缀和 + 暴力解

前面解法①的暴力解法中，时间复杂度太高，其中包括了很多重复计算的操作，比如计算子序列和时，S[i, j]其实可以表示为S[0,j]-S[0, i-1]。用空间换时间，申请长度为n的数组，存储前缀和序列。

复杂度分析

• 时间复杂度： O(n^2)
• 空间复杂度： O(n) 

解法③：动态规划

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)

示例：

思路：只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。

编程注意点：maxSum存储当前最大和；currSum存储当前序列和；curBegin存储当前序列和的起始位置

 
int maxSubSum(const vector<int> & arr,int &begin,int &end)
{
    int maxSum=0;
    int currSum=0;
    int newbegin=0;
    for(int i=0;i<arr.size();i++)
    {
        currSum+=arr[i];
        if(currSum>maxSum)
        {
            maxSum=currSum;
            begin=newbegin;
            end=i;
        }
        if(currSum<0)
        {
            currSum=0;
            newbegin=i+1;
        }
    }
    return maxSum;
}

解法④：分治法

TODO

 

二、最大递增子序列

动态规划法：

设长度为N的数组为{a0，a1, a2, ...an-1)，则假定以aj结尾的数组序列的最长递增子序列长度为L(j)，则L(j)={ max(L(i))+1, i<j且a[i]<a[j] }。也就是说，我们需要遍历在j之前的所有位置i(从0到j-1)，找出满足条件a[i]<a[j]的L(i)，求出max(L(i))+1即为L(j)的值。最后，我们遍历所有的L(j)（从0到N-1），找出最大值即为最大递增子序列。时间复杂度为O(N^2)。

例如给定的数组为{5，6，7，1，2，8}，则L(0)=1, L(1)=2, L(2)=3, L(3)=1, L(4)=2, L(5)=4。所以该数组最长递增子序列长度为4，序列为{5，6，7，8}。

int LIS(int *arr, int n)
{
	int *f = new int[n];
	f[0] = 1;
	for (int i = 1; i < n; i++)
	{
		f[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (arr[i]>arr[j] && f[j]>f[i]-1)   //注意因为可能f[i]是更新后的，因此需减去1比较
				f[i] = f[j] + 1;
		}
	}
	return f[n-1];
}

三、最大公共子序列（Longest Common Subsequence, LCS）

如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子序列，并打印出最长公共子序列。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子序列，则输出它们的长度4，并打印任意一个子序列。

动态规划法：

考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：

（1） 如果am-1==bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；

（2） 如果am-1!=bn-1，则若zk-1!=am-1时，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；

（3） 如果am-1!=bn-1，则若zk-1!=bn-1时，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。

      这样，在找A和B的公共子序列时，如果有am-1==bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。

       求解：
       引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定输出最长公共字串时搜索的方向。
      我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] == Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。

      问题的递归式写成：

      回溯输出最长公共子序列过程：

 

       算法分析：
      由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。

/** 
找出两个字符串的最长公共子序列的长度
** author :liuzhiwei  
** data   :2011-08-15
**/ 
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2, int **b)
{
	int i,j,length1,length2,len;
	length1 = strlen(str1);
	length2 = strlen(str2);
 
	//双指针的方法申请动态二维数组
	int **c = new int*[length1+1];      //共有length1+1行
	for(i = 0; i < length1+1; i++)
		c[i] = new int[length2+1];      //共有length2+1列
 
	for(i = 0; i < length1+1; i++)
		c[i][0]=0;        //第0列都初始化为0
	for(j = 0; j < length2+1; j++)
		c[0][j]=0;        //第0行都初始化为0
 
	for(i = 1; i < length1+1; i++)
	{
		for(j = 1; j < length2+1; j++)
		{
			if(str1[i-1]==str2[j-1])   //由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=0;          //输出公共子串时的搜索方向
			}
			else if(c[i-1][j]>c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]=1;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=-1;
			}
		}
	}
	
	len=c[length1][length2];
	for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组
		delete[] c[i];
	delete[] c;
	return len;
}
void PrintLCS(int **b, char *str1, int i, int j)
{
	if(i==0 || j==0)
		return ;
	if(b[i][j]==0)
	{
		PrintLCS(b, str1, i-1, j-1);   //从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串
		printf("%c",str1[i-1]);        //c[][]的第i行元素对应str1的第i-1个元素
	}
	else if(b[i][j]==1)
		PrintLCS(b, str1, i-1, j);
	else
		PrintLCS(b, str1, i, j-1);
}
 
int main(void)
{
	char str1[100],str2[100];
	int i,length1,length2,len;
	printf("请输入第一个字符串：");
	gets(str1);
	printf("请输入第二个字符串：");
	gets(str2);
	length1 = strlen(str1);
	length2 = strlen(str2);
	//双指针的方法申请动态二维数组
	int **b = new int*[length1+1];
	for(i= 0; i < length1+1; i++)
		b[i] = new int[length2+1];
	len=LCSLength(str1,str2,b);
	printf("最长公共子序列的长度为：%d\n",len);
	printf("最长公共子序列为：");
	PrintLCS(b,str1,length1,length2);
	printf("\n");
	for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组
		delete[] b[i];
	delete[] b;
	system("pause");
	return 0;
}

这里的输出打印函数这里我不是很明白==

四、最长公共子串

最长公共子串 和 最长公共子序列 是有区别的：

     X = <a, b, c, f, b, c>

     Y = <a, b, f, c, a, b>

     X和Y的 最长公共子序列 为<a, b, c, b>，长度为4

     X和Y的 最长公共子串 为 <a, b>长度为2

    其实Substring问题是Subsequence问题的特殊情况，也是要找两个递增的下标序列

    <i1, i2, ...ik> 和 <j1, j2, ..., jk>使

     xi1 == yj1

    xi2 == yj2

    ......

    xik == yjk

    与Subsequence问题不同的是，Substring问题不光要求下标序列是递增的，还要求每次

   递增的增量为1， 即两个下标序列为：

   <i, i+1, i+2, ..., i+k-1> 和 <j, j+1, j+2, ..., j+k-1>

    类比Subquence问题的动态规划解法，Substring也可以用动态规划解决

 令c[i][j]表示x[i]和y[j]为结尾的相同子串的最大长度：

 如  X = <y, e, d, f>，   Y = <y, e, k, f>，则：

   c[1][1] = 1

   c[2][2] = 2

   c[3][3] = 0

   c[4][4] = 1

不难得出递推关系：

   如果xi == yj， 则 c[i][j] = c[i-1][j-1]+1

   如果xi ! = yj,  那么c[i][j] = 0

最后求Longest Common Substring的长度等于   max{  c[i][j],  1<=i<=n， 1<=j<=m}

int LC_substring(char *str1, char *str2)
{
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	int **c = new int*[len1 + 1];
	int i, j;
	for (i = 0; i < len1 + 1; i++)
		c[i] = new int[len2 + 1];
	for (i = 0; i < len1 + 1; i++)
		c[i][0] = 0;
	for (j = 0; j < len2 + 1; j++)
		c[0][j] = 0;
 
	int max = 0;    //记录最长公共子串长度
	int x, y;       //记录公共子串末尾分别在str1，str2的位置
	for (i = 1; i < len1 + 1; i++)
	{
		for (j = 1; j < len2 + 1; j++)
		{
			if (str1[i - 1] == str2[j - 1])
				c[i][j] = c[i - 1][j - 1] + 1;
			else c[i][j] = 0;
			if (c[i][j]>max)
			{
				max = c[i][j];
				x = i;
				y = j;
			}
		}
	}
 
	for (i = 0; i < len1 + 1; i++)
		delete[] c[i];
	delete[] c;
 
	return max;
}

注意上述程序中未输出打印最大子串，可以在更新max值处标记当前最大子串末尾分别在str1与str2中的位置m，n；最后根据max，m，n将子串打印出。