最大子序列&最长公共子串&最长公共子序列

1、最大子序列和

题意

最大子序列和是要找出由数组成的一维数组中和最大的连续子序列。

例如

[www.baidu.com]

{5,-3,4,2}的最大子序列就是 {5,-3,4,2}，它的和是8,达到最大；而 {5,-6,4,2}的最大子序列是{4,2}，它的和是6。

分析

找最大子序列的方法很简单，扫描数组，当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了

class Solution {
public:
    int max_sub(vector<int>& vector)
    {
        int max=0,temp_sum=0;
        for(int i=0;i<vector.size();i++)
        {
            temp_sum+=vector[i];
            if(temp_sum>max)
                max=temp_sum;
            else if(temp_sum<0)
                temp_sum=0;
        }
        return max;
    }
};

2、最长公共子串

题意

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。

例如

“bab”和”caba”的最长公共子串的长度为2

分析

动态规划求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵如下所示：

矩阵的斜对角线最长的那个就是最长公共子串。但是在二维矩阵上找最长的由1组成的斜对角线比较费时的，下面改进：矩阵所在位置的横纵坐标相等时，让它等于其左上角元素加1。

这样矩阵中的最大元素就是最长公共子串的长度。

代码

#define MAX 1000
int res[MAX][MAX];


class Solution {
public:
    int  lcString(string str1,string str2) {
        int i = 0, j = 0;
        int maxlengh = 0;
        for(i = 0; i < str1.size(); ++i)
        {
            for(j = 0; j < str2.size(); ++j) //res[i][j]为最长公共子串的长度
            {
                if(str1[i] == str2[j]){
                    res[i + 1][j + 1] = res[i][j] + 1;
                    maxlengh = max(maxlengh,res[i + 1][j + 1]);
                }
            }
        }
        
        return maxlengh;
    }
};

3、最长公共子序列(LCS)

题意

最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的

例如

ADE和ABCDE的最长公共子序列是ADE,其长度是3。

分析

动态规划法，引进一个二维数组res[][]，用res[i][j]记录X[i]与Y[j] 的LCS 的长度，在计算res[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]。

问题的递归式写成：

代码

#define MAX 1000
int res[MAX][MAX];

class Solution {
public:
    int  lcSubsequence(string str1,string str2) {
        int i = 0, j = 0;
        for(i = 0; i < str1.size(); ++i)
        {
            for(j = 0; j < str2.size(); ++j) //res[i][j]为最长公共子序列的长度
            {
                if(str1[i] != str2[j])
                    res[i + 1][j + 1] = max(res[i + 1][j], res[i][j + 1]);
                else
                    res[i + 1][j + 1] = res[i][j] + 1;
            }
        }

        return res[i][j];
        
    }
};

扩展

1、回文字符串

题意

回文字符串，即从左到右读和从右到左读是完全一样的字符串，比如”asdsa”。当然，给定一个字符串，可在任意位置添加字符，现在要求最少再添加几个字符，可以使这个字符串成为回文字符串。

思路分析

最长公共子序列的变种，将原序列str倒置后得到tmp。求出最长公共子序列的长度，则公共子序列就是回文字串，剩下的就是没有匹配字符的个数。用字符串的总长度减去最长公共子序列的长度，即得到需要添加的字符数量。

代码

#define MAX 1000
int res[MAX][MAX];

class Solution {
public:
    int  palindromeString(string str) {
        int i = 0, j = 0;
        string tmp;
        tmp = str;
        reverse(tmp.begin(), tmp.end()); //倒置
        for(i = 0; i < str.size(); ++i)
        {
            for(j = 0; j < tmp.size(); ++j) //res[i][j]为最长公共子序列的长度
            {
                if(str[i] != tmp[j])
                    res[i + 1][j + 1] = max(res[i + 1][j], res[i][j + 1]);
                else
                    res[i + 1][j + 1] = res[i][j] + 1;
            }
        }

        return (int)(str.size() - res[i][j]);
        
    }
};

2、最长回文字符串

题意

输出字符串中的最长回文字符串

例如

输入字符串 “google”，由于该字符串里最长的对称子字符串是 “goog”，因此输出4。

分析

最长公共子串的变种，将原序列str倒置后得到tmp。求出最长公共子串的长度，则公共子串的长度就是回文字串的长度。

代码

class Solution {
public:
    int  palindromeString(string str) {
        int i = 0, j = 0,maxlengh=0;
        string tmp;
        tmp = str;
        reverse(tmp.begin(), tmp.end()); //倒置
        for(i = 0; i < str.size(); ++i)
        {
            for(j = 0; j < tmp.size(); ++j) //res[i][j]为最长公共子序列的长度
            {
                if(str[i] == tmp[j]){

                    res[i + 1][j + 1] = res[i][j] + 1;
                    maxlengh = max(maxlengh,res[i + 1][j + 1]);
                }
            }
        }
        
        return maxlengh;
        
    }
};