DP问题求解之连续子序列

continous subarrays类型问题是求数组中连续子序列是否满足某些条件的类型问题。

入门级连续子序列

首先先从最简单的连续子数组问题开始，题目详见leetcode 53 Maximum Subarray。

在给定数组（数组中的元素有正有负）中找到有最大sum和的连续子数组。用status[i]记录以第i个元素结尾的，连续子数组的sum和，那么很容易写出状态方程：

status[i] = status[i-1] > 0?(status[i-1]+nums[i]):nums[i]

如果前一个的status[i-1]是负的，那只会对当前的status[i]产生负的影响，所以应直接舍弃，并从当前元素开始重新计算。

注意循环求status数组的时候使用变量记录最大sum和，最终返回即可。

参考代码如下：

    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int status[n+1];
        status[0] = 0;
        int maxValue = nums[0];
        for(int i = 1;i<=nums.size();i++){
            status[i] = max(status[i-1],0)+nums[i-1];
            if(status[i] > maxValue){
                maxValue = status[i];
            }
        }
        return maxValue;
    }

略升级连续子序列

和上面的题型类似，但稍微有一点，题目参考leetcode 152. Maximum Product Subarray。

给定数组中有正有负，得到乘积最大的子序列的值。计算乘积和计算和不同，由于负负得正，所以不但要记录以元素i结尾的最大子序列的值，也需要记录最小子序列的值。写出状态转移方程如下：

status(i,0) = max(status(i-1,0) * nums(i),max(nums(i),status(i-1,1) * nums(i)))

status(i,1) = min(status(i-1,0) * nums(i),min(nums(i),status(i-1,1) * nums(i)))

这样就很容易写出代码，参考代码如下：

int maxProduct(vector<int>& nums) {
        int status[nums.size()][2];
        status[0][0] = nums[0] > 0?nums[0]:0;
        status[0][1] = nums[0] < 0?nums[0]:0;
        int maxValue = nums[0];
        for(int i = 1;i<nums.size();i++){
            status[i][0] = max(status[i-1][0] * nums[i],max(status[i-1][1]*nums[i],nums[i]));
            status[i][1] = min(status[i-1][0]*nums[i],min(status[i-1][1]*nums[i],nums[i]));
            if(status[i][0] > maxValue){
                maxValue = status[i][0];
            }
        }
        return maxValue;
    }

满足条件的连续子序列（一）

下面介绍对要满足某一条件的连续子序列的求解方法，如leetcode 560 Subarray Sum Equals K。严格的来说这不是一道DP问题，但是这道题的思路对后面问题的求解有借鉴意义。

求出给定数组中连续子序列的和为K的子序列个数。采用prefix sum的方法（prefix sum就是当前元素及其之前元素的和），用一个map记录所有元素的prefix sum和对应个数（由于数组中元素可为负，所以会出现某几个元素的prefix sum相等的情况）。记某个元素的前缀和为sum(i)，若sum(i)-K出现在map中则说明存在某个子序列其和为K。这时候只需要将map[sum(i)-k]的值加入count中即可。

参考代码如下：

int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> res;
        int count = 0;
        int sum = 0;
        res[0] = 1;
        for(int i = 0;i<nums.size();i++){
            sum += nums[i];
            if(res.find(sum-k) != res.end()){
                count += res[sum-k];
            }
            res[sum]++;
        }
        return count;
    }

满足条件的连续子序列（二）

有了上一道题的思路基础，更进一步的来看参考leetcode 523. Continuous Subarray Sum。

给定一个非负数组，判断数组中是否有连续子序列的和为K的整数倍，且子序列的元素个数应大于等于2。这道题的特殊情况比较多。

还是利用prefix sum记录前缀和，但不同的是，对前缀和和K进行余数处理并保存在map中，如果发现余数在map中曾经出现过则说明，其中必有子序列是K的整数倍，但这里还需要对下标间隔进行判断，所以map中的key为余数，value为当前元素的下标。

特殊情况的说明：

• k可以为0，当k为0的时候，求余运算会出错
• 数组中的元素可以为0，0%任何数都为0，即整除。

由于这道题个人觉得可参考的地方很多，下面给出代码和解释：

bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> res;
        int sum = 0; 
        //初始化这个值为-1，避免在数组中只有两个元素时出错。
        res[0] = -1; 
        for(int i = 0;i<nums.size();i++){
            sum += nums[i];
            if(k != 0){
                sum = sum % k;
            }
          //这里一定要注意只有在此余数没有出现过的时候更新res，避免当数组中的元素都为0的时候一直在更新res中的值，而返回false。
            if(res.find(sum) != res.end()){
              //如果模拟过前面思路的计算过程，就会发现真正连续子序列是从res[sum]+1开始的，所以限制条件里没有等于。
                if(i - res[sum] > 1){
                    return true;
                }
            }
            else{
                res[sum] = i;
            }
        }
        return false;
    }

满足条件的连续子序列（三）

类似的还有使连续子序列的乘积满足某个条件的，如leetcode 713.Subarray Product Less Than K。

在给定的正数数组中返回所有乘积小于K的子序列的个数。采用滑动窗口，窗口内的元素乘积小于K，并使用start记录滑动窗口的头部下标，一旦滑动窗口中的元素的乘积大于等于K了，则就需要将start向后移动。

需要注意的是在移动过程中对满足条件的子序列的个数的记录，实际上滑动窗口每增加一个元素，相当于增加了(i-start+1)个满足条件子序列，按此规律进行累加。

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int count = 0;
        int product = 1;
        int start = 0;
        for(int i = 0;i<nums.size();i++){
            product *= nums[i];
            while(start <= i && product >= k){
                product /= nums[start];
                start++;
            }
            count += i - start + 1;
        }
        return count;
    }

满足条件的连续子序列（四）

和上面的那道题思路很类似，也是使用滑动窗口来解，题目详见leetcode 209. Minimum Size Subarray Sum。

从给定正数组中，找到相加大于等于K的最短子序列。同样的用一个滑动窗口，且窗口内的元素相加小于K，同时用start记录滑动窗口的头部，当滑动窗口内的元素大于等于K时，向后移动start，并更新最短子序列的值。

参考代码如下：

int minSubArrayLen(int s, vector<int>& nums) {
        int len = (int)nums.size()+1;
        int sum = 0;
        int start = 0;
        for(int i = 0;i<(int)nums.size();i++){
            sum += nums[i];
            while(sum >= s){
                if(i-start+1 < len){
                    len = i-start+1;
                }
                sum -= nums[start];
                start++;
            }
        }
        if(len == (int)nums.size()+1){
            return 0;
        }
        return len;
    }

多数组的连续子序列

上面介绍的都是单数组的连续子序列问题，其实多数组问题也很经典，比如leetcode 718 Maximum Length of Repeated Subarray。

判断两个给定数组中的最长连续子序列，这种题是典型的可以用空间换取时间来解决的，使用一个二维数组status(i,j)当前位置的最长子序列的长度，很容易写出状态转移方程：

status(i,j) = status(i-1,j-1)+1 if A[i]=B[j]

同时使用变量在循环的时候更新记录最长子序列的长度最终返回即可。

参考代码如下：

    int findLength(vector<int>& A, vector<int>& B) {
        int len1 = (int)A.size();
        int len2 = (int)B.size();
        int status[len1+1][len2+1];
        memset(status,0,sizeof(status));
        int maxValue = 0;
        for(int i = 1;i<=len1;i++){
            for(int j = 1;j<=len2;j++){
                if(A[i-1] == B[j-1]){
                    status[i][j] = status[i-1][j-1]+1;
                    if(status[i][j] > maxValue){
                        maxValue = status[i][j];
                    }
                }
            }
        }
        return maxValue;
    }