Maximum Subarray问题_最大子数组的和

Fri Oct 09 17:41:07 CST 2015 680 算法

文章摘要给定一个数组,求出和最大的子数组。比如, 给定数组[−2,1,−3,4,−1,2,1,−5,4],子数组[4,−1,2,1] 有最大和为6

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.

关键思路:

遍历一次数组,用两个变量currentSum和largestSum分别表示当前和与当前已知最大和;

若某一步发现currentSum<0,则将当前数组的值赋给currentSum,因为currentSum为负数的话它加上下一个数的和肯定不会比下一个数大;若currentSum>0则currentSum+=数组当前值;

若某一步发现currentSum>largestSum,则largestSum=CurrentSum;

返回largestSum;


public class Solution {
    public int maxSubArray(int[] A) {
        if(A.length == 0) return 0;        //注意细节
        int currentSum = A[0];             //第一个数
        int largestSum = A[0];             //第一个数
        
        for(int i = 1; i < A.length; i++){ //开始遍历 
            if(currentSum < 0){            //若当前和小于0
                currentSum = A[i];
            }
            else{
                currentSum += A[i];
            }

            if(currentSum >= largestSum){
                largestSum = currentSum;
            }
        }
        return largestSum;
    }
}


打赏
打赏

分享到: