一起刷leetcode(53):Maximum Subarray


原题:https://oj.leetcode.com/problems/maximum-subarray/
编号:53
题目描述:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

最大连续子序列和,非常经典的题。
已邀请:

July - 抠细节抠体验,不妥协不将就。

赞同来自: M_Kepler 青原行思 米修


OK,刚好我今年计划出版的新书(暂定书名为:程序员编程艺术 - 面试和算法心得)有写到此题,便截取下来,好班门弄斧一把。

中文描述
给定一个整数数组,数组里可能有正数、负数和零。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18。

分析与解法
解法一:暴力枚举
求一个数组的最大子数组和,最直观最野蛮的办法便是,三个for循环三层遍历,求出数组中每一个子数组的和,最终求出这些子数组和的最大的一个值。 令currSum[i, …, j]为数组A中第i个元素到第j个元素的和(其中0 <= i <= j < n),maxSum为最终求得的最大连续子数组的和。
且当全是负数的情况时,可以让程序返回0,也可以让程序返回最大的那个负数,这里,让程序返回最大的那个负数。
    //下面这段代码由于复杂度比较高,所以在leetcode上测试时超时
    class Solution {
    public:
        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;
        }
    };

解法二:动态规划
事实上,可以令currSum是以当前元素结尾的最大子数组和,maxSum是全局的最大子数组和,当往后扫描时,对第j个元素有两种选择:要么放入前面找到的子数组,要么做为新子数组的第一个元素:如果currSum > 0,则令currSum加上a[j],反之,currSum < 0 时,则currSum 被置为当前元素,即currSum = a[j]。

相当于如果设currSum(j)为以j结尾的最大连续子数组和,那么currSum(j) = max{0, currSum[j - 1]} + a[j]。且当maxSum < currSum时,则更新maxSum = currSum,否则maxSum保持原值,不更新。
举个例子,当输入数组是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
参考代码如下:
    //已经AC
    class Solution {
    public:
        int maxSubArray(int A[], int n) {
            int currSum = 0;
            int maxSum = A[0];       //全负情况,返回最大数

            for (int j = 0; j < n; j++)
            {
                if (currSum >= 0)
                    currSum += A[j];
                else
                    currSum = A[j];
                if (currSum > maxSum)
                {
                    maxSum = currSum;
                }
            }
            return maxSum;
        }
    };

此方法从前往后扫描一遍数组,即完成求最大连续子数组和的需求,所以时间复杂度为O(n)。

问题变形
1.如果要你求最大连续子数组和,同时也要求输出所求子数组的开始位置和结束位置呢?
2.如果要你求最大子数组和,但不要求子数组是连续的呢?
3.如果数组是二维数组,同样要你求最大连续子数组的和呢?
4.如果是要你求连续子数组的最大乘积呢?

还有很多举一反三的题,便不列了。

要回复问题请先登录注册

返回顶部