文档章节

Maximum Subarray 最大子数组

writeademo
 writeademo
发布于 2017/09/08 18:05
字数 479
阅读 10
收藏 0

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

    }

}

复制代码

 

本文转载自:http://www.cnblogs.com/grandyang/p/4377150.html

共有 人打赏支持
writeademo
粉丝 23
博文 485
码字总数 179357
作品 0
东城
Lintcode42 Maximum Subarray II solution 题解

【题目描述】 Given an array of integers, find two non-overlapping subarrays which have the largest sum.The number in each subarray should be contiguous.Return the largest sum. N......

abcdd1234567890
06/29
0
0
Lintcode41 Maximum Subarray solution 题解

【题目描述】 Given an array of integers, find a contiguous subarray which has the largest sum. Notice:The subarray should contain at least one number. 给定一个整数数组,找到一个......

abcdd1234567890
06/29
0
0
动态规划法(八)最大子数组问题(maximum subarray problem)

问题简介   本文将介绍计算机算法中的经典问题——最大子数组问题(maximum subarray problem)。所谓的最大子数组问题,指的是:给定一个数组A,寻找A的和最大的非空连续子数组。比如,数...

jclian91
06/06
0
0
子数组的最大乘积 Maximum Product Subarray

问题: Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array , the contiguous subarray has th......

叶枫啦啦
2017/11/07
0
0
和最大的连续子数组 Maximum Subarray

问题: Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array , the contiguous subarray has the la......

叶枫啦啦
2017/06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

windbg调试C源码级驱动

联机方式不多说了。我博客里有,英文的。 windbg联机文档 https://docs.microsoft.com/zh-cn/windows-hardware/drivers/debugger/debug-universal-drivers---step-by-step-lab--echo-kernel......

simpower
35分钟前
0
0
redis快照和AOF简介

数据持久化到硬盘:一是快照(snapshotting),二是只追加文件(append-only file AOF) 快照 核心原理:redis某个时间内存内的所有数据写入硬盘 场景:redis快照内存里面的数据 1. 用户发送bgsav...

拐美人
35分钟前
0
0
这个七夕,送你一份程序员教科书级别的告白指南

给广大爱码士们的高能预警: 今天,就是七夕了…… (单身非作战人群请速速退场!) 时常有技术GG向个推君抱怨 经过网民多年的教育 以及技术人持之以恒的自黑 冲锋衣狂热分子·格子衫骨灰级粉...

个推
40分钟前
0
0
python爬虫日志(15)cookie详解

转载:原文地址 早期Web开发面临的最大问题之一是如何管理状态。服务器端没有办法知道两个请求是否来自于同一个浏览器。那时的办法是在请求的页面中插入一个token,并且在下一次请求中将这个...

茫羽行
41分钟前
0
0
qlv视频格式转换器

  腾讯视频中的视频影视资源有很多,小编经常在里面下载视频观看,应该也有很多朋友和小编一样吧,最近热播的电视剧也不少,如《香蜜沉沉烬如霜》、《夜天子》还有已经完结的《扶摇》,这么...

萤火的萤火
44分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部