53. Maximum Subarray

 

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

 

这道题让求最大子数组之和,并且要用两种方法来解,分别是 O(n) 的解法,还有用分治法 Divide and Conquer Approach,这个解法的时间复杂度是 O(nlgn),那就先来看 O(n) 的解法,定义两个变量 res 和 curSum,其中 res 保存最终要返回的结果,即最大的子数组之和,curSum 初始值为0,每遍历一个数字 num,比较 curSum + num 和 num 中的较大值存入 curSum,然后再把 res 和 curSum 中的较大值存入 res,以此类推直到遍历完整个数组,可得到最大子数组的值存在 res 中,代码如下:

 

C++ 解法一:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN, curSum = 0;
        for (int num : nums) {
            curSum = max(curSum + num, num);
            res = max(res, curSum);
        }
        return res;
    }
};

 

Java 解法一:

public class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE, curSum = 0;
        for (int num : nums) {
            curSum = Math.max(curSum + num, num);
            res = Math.max(res, curSum);
        }
        return res;
    }
}

 

题目还要求我们用分治法 Divide and Conquer Approach 来解,这个分治法的思想就类似于二分搜索法,需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,求出的最大值分别和左右两边得出的最大值相比较取最大的那一个,代码如下:

 

C++ 解法二:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) return 0;
        return helper(nums, 0, (int)nums.size() - 1);
    }
    int helper(vector<int>& nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int lmax = helper(nums, left, mid - 1);
        int rmax = helper(nums, mid + 1, right);
        int mmax = nums[mid], t = mmax;
        for (int i = mid - 1; i >= left; --i) {
            t += nums[i];
            mmax = max(mmax, t);
        }
        t = mmax;
        for (int i = mid + 1; i <= right; ++i) {
            t += nums[i];
            mmax = max(mmax, t);
        }
        return max(mmax, max(lmax, rmax));
    }
};

 

Java 解法二:

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        return helper(nums, 0, nums.length - 1);
    }
    public int helper(int[] nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int lmax = helper(nums, left, mid - 1);
        int rmax = helper(nums, mid + 1, right);
        int mmax = nums[mid], t = mmax;
        for (int i = mid - 1; i >= left; --i) {
            t += nums[i];
            mmax = Math.max(mmax, t);
        }
        t = mmax;
        for (int i = mid + 1; i <= right; ++i) {
            t += nums[i];
            mmax = Math.max(mmax, t);
        }
        return Math.max(mmax, Math.max(lmax, rmax));
    }
}

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/53

 

类似题目:

Best Time to Buy and Sell Stock

Maximum Product Subarray 

Degree of an Array

Longest Turbulent Subarray

 

参考资料:

https://leetcode.com/problems/maximum-subarray/

https://leetcode.com/problems/maximum-subarray/discuss/20211/Accepted-O(n)-solution-in-java

https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts

https://leetcode.com/problems/maximum-subarray/discuss/20200/Share-my-solutions-both-greedy-and-divide-and-conquer

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation