递归与分治 / 序列DP | 最大子数组问题

川长思鸟来 2023-07-11 15:22 2阅读 0赞

> 问题：寻找数组A\[ l..r \] 中各元素之和最大的连续非空子数组。我们称这样的数组叫最大子数组。

本文将给出三种解法：暴力求解、分治、动态规划。时间复杂度依次递减。

--------------------

为了方便函数传出结果，我们定义一个结构体来储存最大子数组的要素，即该子数组在原数组的下标界限和对应的和。

typedef struct subArray {
        int l;  //子数组的左边界
        int r;  //子数组的右边界
        int sum;  //子数组每一项的和
    } SUB_ARRAY;

--------------------

# 方法一：暴力求解法 —— ![O(n^2)][O_n_2]  #

显然，需要两个for循环来遍历原数组所有的子数组，时间复杂度相当高。

这个思路太差，就不上代码了。

--------------------

# 方法二：分治法 —— ![O(nlgn)][O_nlgn] #

### 1、分（Divide） ###

我们要寻找一个数组 a\[l, r\] 的最大子数组，我们可以将该数组分解成两个规模尽量相等的子数组。即找到数组的中央位置mid，然后将其划分为左子数组 a\[l, mid\] 和 右子数组a\[mid + 1, r\] 来考虑。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

### 2、治（Conquer） ###

那么a\[l, r\] 的子数组有三种存在方式，在左子数组内、在右子数组内、跨越中点的数组。那么应该在这三个范围里找最大子数组，前面两者我们可以通过递归地调用求解，因为这两个子问题仍然是一般情况下求最大子数组问题，只是规模更小。那么寻找跨越中点的最大子数组，我们可以单独写一个函数，在O(n)时间内，从mid向两侧遍历即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

完整代码如下：

// Created by A on 2020/3/5.
    
    #include <climits>
    typedef struct subArray {
        int l;  //子数组的左边界
        int r;  //子数组的右边界
        int sum;  //子数组每一项的和
    } SUB_ARRAY;
    
    /* 在数组a[l,r]内找到包含m下标位置的最大子数组 */
    SUB_ARRAY FindMaxCrossingSubarray(int a[], int l, int m, int r) {
        /* 计算从m出发的左半边数组的最大子数组 */
        int leftMax = INT_MIN, leftIndex, t = 0;
        for (int i = m; i >= l; i--) {
            t += a[i];
            if (t > leftMax) {
                leftIndex = i;  //最大位置对应的下标
                leftMax = t;  //最大和
            }
        }
        t = 0;
        /* 计算从m + 1出发的右半边数组的最大子数组 */
        int rightMax = INT_MIN, rightIndex;
        for (int i = m + 1; i <= r; i++) {
            t += a[i];
            if (t > rightMax) {
                rightIndex = i;  //最大位置对应的下标
                rightMax = t;  //最大和
            }
        }
        SUB_ARRAY ans;
        ans.l = leftIndex;
        ans.r = rightIndex;
        ans.sum = leftMax + rightMax;
        return ans;
    }
    /* 在数组a[l,r]内找到最大子数组（非空!） */
    SUB_ARRAY FindMaxSubarray(int a[], int l, int r) {
        /* 递归的终点，数组只有一个元素 */
        if(l == r) {
            SUB_ARRAY ans;
            ans.l = ans.r = l;
            ans.sum = a[l];
            return ans;  //直接将原数组作为最大子数组返回
        }
        int mid = (l + r) / 2;  //中间位置
        SUB_ARRAY leftAns = FindMaxSubarray(a, l, mid); //递归地求mid左侧的最大子数组
        SUB_ARRAY rightAns = FindMaxSubarray(a, mid + 1, r);  //递归地求mid右侧地最大子数组
        SUB_ARRAY midAns = FindMaxCrossingSubarray(a, l, mid, r);  //求包含mid地最大子数组
        /* 返回三者中和最大的 */
        if(leftAns.sum > midAns.sum && leftAns.sum > rightAns.sum)
            return leftAns;
        else if(midAns.sum > rightAns.sum)
            return midAns;
        else
            return rightAns;
    }

--------------------

# 方法三：动态规划法 —— ![O(n)][O_n]  #

### 1、算法描述  ###

这个是一个很棒的非递归、线性时间复杂度的方法：

若已知数组 a\[0..j\] 的最大子数组，那么 a\[0..j+1\] 的最大子数组为下面两种情况之一:

1.  不包含第j + 1项：即为数组 a\[0..j\] 的最大子数组
2.  包含第j+1项：a\[k..j+1\] (其中 0<= k <= j + 1)

### 2、算法实现 ###

从头开始循环遍历数组a，遍历到的下标索引为 i ：用cur记录 a\[ 0..i \] 内**包含第 i 项**的最大子数组，用ans记录 a\[ 0..i \] 内的最大子数组。*(下面解释时用cur()、ans()分别表示两个变量，括号内为遍历到下标索引，来代表在遍历到这个位置所对应的cur与ans。)*

若已知 cur(i) 和 ans(i)，那么继续遍历下一个元素：

1.  根据cur 的定义，cur(i+1) 应该是 cur(i) + a\[ i + 1\] 和 a\[ i + 1\] 中的较大值
2.  根据算法描述中说的：ans(i+1)应该是cur(i+1) 和 ans(i)中的较大值。那么遍历完毕的 ans 就是答案。

下面是一张遍历的具体算法图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2][]

算法理解了，代码就很简单了：

#include <climits>
    typedef struct subArray {
        int l;  //子数组的左边界
        int r;  //子数组的右边界
        int sum;  //子数组每一项的和
    } SUB_ARRAY;
    
    
    /* 在数组a[l,r]内找到最大子数组（非空!） */
    SUB_ARRAY FindMaxSubarray1(int a[], int l, int r) {
        int ans = INT_MIN, cur = INT_MIN;
        int curLeft, leftIndex, rightIndex;  //记录cur对应的子数组左下标、记录ans对应的子数组左右下标
        for (int i = l; i <= r; i++) {
            /* 找到a[ 0..i ]内包含第i项的最大子数组 */
            if (cur + a[i] >= a[i])
                cur += a[i];
            else {
                cur = a[i];
                curLeft = i;
            }
            /* 更新a[ 0..i ]内的最大子数组 */
            if (cur > ans) {
                ans = cur;
                leftIndex = curLeft;
                rightIndex = i;
            }
        }
        /* 返回答案 */
        SUB_ARRAY result;
        result.l = leftIndex;
        result.r = rightIndex;
        result.sum = ans;
        return result;
    }

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3]

[O_n_2]: https://private.codecogs.com/gif.latex?O%28n%5E2%29
[O_nlgn]: https://private.codecogs.com/gif.latex?O%28nlgn%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306132848804.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200306133007687.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[O_n]: https://private.codecogs.com/gif.latex?O%28n%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200306144856969.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200111020715220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70