Java for LeetCode 053 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.

解题思路:

本题目是《算法导论》 4.1 节 最大子数组的原题,书本上给出的是分治的做法,练习4.1-5给出了线性时间的算法,大致归结如下:一次遍历肯定能搞定问题,只需使用一个sum计算遍历下来可能的最大的和,一个maxSum记录数目的最大值,maxSum即为所求,JAVA实现如下:

static public int maxSubArray(int[] nums) {
int sum=nums[0],maxSum=sum;
for(int i=1;i<nums.length;i++){
if(sum<=0)
sum=nums[i];
else
sum+=nums[i];
maxSum=Math.max(maxSum, sum);
}
return maxSum;
}
上一篇:九、Linux 磁盘管理


下一篇:Tutorial 5: Relationships & Hyperlinked APIs