zzys

首先子数组是连续的，子序列是不一定连续的。

一个序列代表是求一个序列的最长子数组或子序列，而两个序列指的是求两个序列的最长公共子数组或子序列。

同时，在这四种情况中，长度为1也是一个递增子序列。

一个序列两个序列
子数组最长连续递增序列open in new window最长重复子数组open in new window
子序列最长递增子序列open in new window最长公共子序列open in new window

在解题时，我们通常将一个序列问题的dp数组的i j定义为下标，而两个序列问题的dp数组的i j定义为长度。

最长连续递增序列

dp定义

dp[i]代表下标为i的前面的序列的最长递增序列。

转移方程

if(nums[i] > nums[i - 1]) dp[i] = max(dp[i], dp[i - 1]);
else dp[i] = 1;

如果前后相等，那么最长递增子序列长度加一，如果不相等，那么最长递增子序列的长度就要变为一。

注意第二步实际可以省略，可以在初始化时全部初始化为1。

初始化

for(int i = 0; i < nums.size(); i ++) {
    dp[i] = 1;
}

每一个元素单独都是一个连续递增序列。

遍历

很明显，计算i时需要i-1的数据，所以需要正序遍历。同时起点是1，因为需要和i-1比较。

for(int i = 1;i < nums.size(); i ++) {
    if(nums[i] > nums[i - 1]) dp[i] = max(dp[i], dp[i - 1] + 1);
    reuslt = max(reuslt, dp[i]);
}

注意最长连续递增序列不一定以最后一个元素结尾，所以我们需要定义result，来确定dp中的最大值。

代码

int dp[10010];
int findLengthOfLCIS(vector<int>& nums) {
    for(int i = 0; i < nums.size(); i ++) {
        dp[i] = 1;
    }
    int reuslt = 1;
    for(int i = 1;i < nums.size(); i ++) {
        if(nums[i] > nums[i - 1]) dp[i] = max(dp[i], dp[i - 1] + 1);
        else dp[i] = 1;
        reuslt = max(reuslt, dp[i]);
    }
    return reuslt;
}

其它解法

本题可以不用dp，直接记录起点终点也可以。

int findLengthOfLCIS(vector<int>& nums) {
    int start = 0;
    int end = 0;
    int result = 1;
    for(int i = 1; i < nums.size(); i ++) {
        if(nums[i] > nums[i - 1]) {
            end ++;
        }else{
            start = i;
            end = i;
        }
        result = max(result, end - start + 1);
    }
    return result;
}

最长递增子序列

dp定义

dp[i]代表前i个字符组成的序列的最长递增子序列。

转移方程

if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
else {}

这里的j实际上就是(i - 1) (i -2) ... (i - i) 的集合，因为不一定要连续，所以不是只由前一个的状态推导而来。

初始化

for(int i = 0; i < nums.size(); i ++) {
    dp[i] = 1;
}

每一个元素单独都是一个连续递增序列。

遍历

在这里就需要两重循环，内部循环是用来遍历一个状态的所有前导状态。

在计算状态时需要前面的状态，所以正序遍历。

for(int i = 1; i < nums.size(); i ++) {
    for(int j = 0; j < i; j ++) {
        if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
    }
    result = max(result, dp[i]);
}

代码

int dp[2510];
int lengthOfLIS(vector<int>& nums) {
    for(int i = 0; i < nums.size(); i ++) dp[i] = 1;
    int result = 1;
    for(int i = 1; i < nums.size(); i ++) {
        for(int j = 0; j < i; j ++) {
            if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
        result = max(result, dp[i]);
    }
    return result;
}

其他解法

维护一个tail子数组，保证tail数组的单调性，在维护tail数组的过程中，tail数组能够到达的最大长度就是该序列的最长子序列。注意，tail数组中的元素并非满足子序列的定义。

我们在遍历nums过程中，维护tail数组，规则如下：

  • 对nums[i]在tail中二分，获取到位置x
  • 使用nums[i]覆盖tail[x]
  • 如果x的大小等于当前维护的长度，那么就将长度加一（因为最大下标 == 长度-1）
// 获取第一个比target大的数
// 如果元素不存在，那么我们就获取到的是比它大的元素的下标
// 	这样最大可能的保证了tail能取到更大的长度的可能
int bs_left(vector<int>& nums, int target, int start, int end) {
    int i = start,j = end;
    while(i < j) {
        int mid = i + j >> 1;
        if(nums[mid] >= target) j = mid;
        else i = mid + 1;
    }
    return i;
}  
int lengthOfLIS(vector<int>& nums) {
    vector<int> tail(nums.size());
    int len = 0;
    for(int i = 0; i < nums.size(); i ++) {
        int x = bs_left(tail, nums[i], 0, len);
        // 可以重复就计算右边界
        // int x = bs_right(tail, nums[i], 0, len);
        tail[x] = nums[i];
        if(len == x) len ++;
    }
    return len;
}

最长重复子数组

本题是给定两个序列，求两个序列的最长公共子数组，子数组必须是连续的。

dp定义

dp[i][j]代表nums1[:i]和nums2[:j]的最长重复子数组，i j代表长度。

转移方程

if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = 0;

同样第二步可以忽略。

初始化

当两个序列，任意一个序列的长度为0时，它们的最长重复子数组长度一定是零，我们将dp定义为全局变量，省去初始化。

遍历

两个循环都要从1开始。

同时result需要每次都去更新。

for(int i = 1; i <= nums1.size(); i ++) {
    for(int j = 1; j <= nums2.size(); j ++) {
        if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = 0;
        result = max(result, dp[i - 1][j - 1] + (nums1[i - 1] == nums2[j - 1]));
    }
}

代码

int dp[1010][1010];

int findLength(vector<int>& nums1, vector<int>& nums2) {
    int result = 0;
    for(int i = 1; i <= nums1.size(); i ++) {
        for(int j = 1; j <= nums2.size(); j ++) {
            if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            result = max(result, dp[i][j]);
        }
    }
    return result;
}

优化

可以优化为一维，首先要注意遍历顺序要倒序，其次当条件不满足时，必须手动将dp[j]清零，不然会有脏数据。

int dp[1010];
int findLength(vector<int>& nums1, vector<int>& nums2) {
    int result = 0;
    for(int i = 1; i <= nums1.size(); i ++) {

        for(int j = nums2.size(); j >= 1; j --) {
            if(nums1[i - 1] == nums2[j - 1]) dp[j] =  dp[j - 1] + 1;
            else dp[j] = 0;
            result = max(result, dp[j]);
        }
    }
    return result;
}

最长公共子序列

相较于上一题，子序列不一定是连续的。

dp定义

dp[i][j]代表nums1[:i]和nums2[:j]的最长重复子序列，i j代表长度。

转移方程

if(nums1[i - 1] == nums[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

第一步和上一题相同，关键是第二步。

由于子序列的缘故，当i - 1 != j - 1时，我们不能单纯的认为当前的dp[i][j]就为0，因为dp[i - 1][j - 1]只是它的其中一个前导状态，它还有dp[i][j -1]和dp[i -1][j]这两个前导状态。

初始化

当两个序列，任意一个序列的长度为0时，它们的最长重复子数组长度一定是零，我们将dp定义为全局变量，省去初始化。

遍历

for(int i = 1; i <= text1.size(); i ++) {
    for(int j = 1; j <= text2.size(); j ++) {
        if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
}

代码

int dp[1010][1010];
int longestCommonSubsequence(string text1, string text2) {
    for(int i = 1; i <= text1.size(); i ++) {
        for(int j = 1; j <= text2.size(); j ++) {
            if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[text1.size()][text2.size()];
}
上次更新:
Contributors: YangZhang