## Maximum Subarray 最大子数组 转

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.

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;

}

}

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

}

}

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

jclian91
06/06
0
0

2017/11/07
0
0

2017/06/05
0
0

CentOS配置Tomcat监听80端口,虚拟主机

Tomcat更改默认端口为80 更改的配置文件是: /usr/local/tomcat/conf/server.xml [root@test-a ~]# vim /usr/local/tomcat/conf/server.xml # 找到 Connector port="8080" protocol="HTTP/1......

5
0
《稻盛和夫经营学》读后感心得体会3180字范文

《稻盛和夫经营学》读后感心得体会3180字范文： 一代日本经营之圣稻盛和夫凭借刻苦勤奋的精神以及深植于佛教的商业道德准则，成为了“佛系”企业家的代表人物。在《稻盛和夫经营学》“领导人...

3
0
java框架学习日志-5（常见的依赖注入）

4
0

mbzhong

2
0
ActiveMQ消息传送机制以及ACK机制详解

AcitveMQ是作为一种消息存储和分发组件，涉及到client与broker端数据交互的方方面面，它不仅要担保消息的存储安全性，还要提供额外的手段来确保消息的分发是可靠的。 一. ActiveMQ消息传送机...

watermelon11

2
0