菜鸟系列之C/C++经典试题(二)

﹏ヽ暗。殇╰゛Y 2022-08-11 05:30 120阅读 0赞

**求子数组的最大和**

**题目描述：** 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4,7, 2，因此输出为该子数组的和18。

这个问题在各大公司面试中出现频率之频繁，被人引用次数之多，非一般面试题可与之匹敌。ok，下面，咱们来一步一步分析这个题。

**分析与解法**

**解法一**

求一个数组的最大子数组和，我想最直观最野蛮的办法便是，三个for循环三层遍历，求出数组中每一个子数组的和，最终求出这些子数组的最大的一个值。令currSum\[i, …, j\]为数组A中第i个元素到第j个元素的和（其中0 <= i <= j < n），maxSum为最终求到的最大连续子数组的和。

且当全是负数的情况时，我们可以让程序返回0，也可以让程序返回最大的那个负数，这里，我们让程序返回最大的那个负数。

参考代码如下：

int MaxSubArray(int* A, int n)
    {
        int maxSum = a[0];  //全负情况，返回最大负数
        int currSum = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                for (int k = i; k <= j; k++)
                {
                    currSum += A[k];
                }
                if (currSum > maxSum)
                    maxSum = currSum;
    
                currSum = 0; //这里要记得清零，否则的话sum最终存放的是所有子数组的和。
            }
        }
        return maxSum;
    }

这个实现的复杂度是O(3)

**解法二**

事实上，当我们令currSum为当前最大子数组的和，maxSum为最后要返回的最大子数组的和，当我们往后扫描时，

*  对第i+1个元素有两种选择：要么放入前面找到的子数组，要么做为新子数组的第一个元素；

· 如果currSum加上当前元素a\[j\]后currSum变大了，则令currSum加上a\[j\]，否则currSum重新赋值，置为下一个元素，即currSum = a\[j\]。

*  同时，当currSum > maxSum，则更新maxSum = currSum，否则保持原值，不更新。

即：

currSum = max(a[j], currSum + a[j])

maxSum = max(maxSum, currSum)

，当输入数组是 1, -2, 3, 10, -4, 7, 2, -5 ，那么，currSum和maxSum相应的变化为：

*  currSum： 0 1 - 1 3 13 9 16 18 13
 *  maxSum ： 0 1 1 3 13 13 16 18 18

参考代码如下：

//本段代码引自编程之美
    int MaxSum(int* A, int n)
    {
        int maximum = -INF;
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                for (int k = i; k <= j; k++)
                {
                    sum += A[k];
                }
                if (sum > maximum)
                    maximum = sum;
    
                sum = 0; //这里要记得清零，否则的话sum最终存放的是所有子数组的和。也就是编程之美上所说的bug。多谢苍狼。
            }
        }
        return maximum;
    }

**问题扩展**

*  如果数组是二维数组，同样要你求最大子数组的和列?
 *  如果是要你求子数组的最大乘积列?
 *  如果同时要求输出子段的开始和结束列?

**举一反三**

1 给定整型数组，其中每个元素表示木板的高度，木板的宽度都相同，求这些木板拼出的最大矩形的面积。并分析时间复杂度。

此题类似leetcode里面关于连通器的题，需要明确的是高度可能为0，长度最长的矩形并不一定是最大矩形，还需要考虑高度很高，但长度较短的矩形。如\[5,4,3,2,4,5,0,7,8,4,6\]中最大矩形的高度是\[7,8,4,6\]组成的矩形，面积为16。

2、环面上的最大子矩形

《算法竞赛入门经典》 P89 页。

3、最大子矩阵和

一个M\*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。如果所有数都是负数，就输出0。例如：3\*5的矩阵：

1 2 0 3 4

2 3 4 5 1

1 1 5 3 0