Leetcode_53_Maximum Subarray

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/43989997

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.

思路：

（1）题意为给定整数数组，求解数组中连续子数组之和的最大值。

（2）这是一道比较经典的笔试面试题。主要考查对数组的运用。由于数组中的元素可能为正，也可能为负，所以，要得到连续元素的最大值，需对数组遍历过程中出现负值时进行判断。这样，只需遍历数组一次（初始化当前连续序列之和sum=0，最大值max=x[0]），在遍历的过程中，如果当前sum>=0，说明连续序列之和为正，将当前遍历元素的数值加到sum中；如果sum<0，说明在之前遍历过程中遇到了负数，将当前遍历元素的数值赋给sum；如果sum比当前最大值max要大，则将sum的值赋给max；遍历完数组后，max即为所求。

（3）该题主要需考虑正负数交替的情况以及全是负数的情况，详情参见下方代码。希望本文对你有所帮助。

算法代码实现如下：

/** * @author liqq */public class Maximum_Subarray{ public int maxSubArray(int[] x) { if(x==null || x.length==0) return 0;int sum = 0;int max = x[0];for (int i = 0; i < x.length; i++) {if(sum>=0){sum = sum+x[i];}else{sum=x[i];}if(sum>max){max = sum;}}//for (int i = 0; i < x.length; i++) {//for (int j = i; j < x.length; j++) {//for (int k = i; k <= j; k++) {//sum = sum + x[k];//}//if(MaxSum<sum){//MaxSum = sum;//}//sum=0;//}//}return max; }}