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;

  }

巴特西

Java for LeetCode 053 Maximum Subarray

最新文章

热门文章