Maximum Subarray 最大子数组
Maximum Subarray 最大子数组
writeademo 发表于3个月前
Maximum Subarray 最大子数组
  • 发表于 3个月前
  • 阅读 9
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

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.

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.

 

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

复制代码

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

 

复制代码

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));

    }

}

复制代码

 

共有 人打赏支持
粉丝 18
博文 375
码字总数 156640
×
writeademo
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: