• 在LeetCode上做的一道題目，想了很久沒有想出比較簡便的方法，借鑒了網(wǎng)上的方法之后做了然后做個總結(jié)。

題目描述：

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.
簡單而言就是找出一個正負數(shù)都有的數(shù)組中最大的子數(shù)組之和。

分析解答：

1. 看到這個題，首先想到的一個最簡單但是時間復(fù)雜度最高的方法就是，把這個數(shù)組的所有子數(shù)組的和都求出來，一個一個比較，取最大值。
   假設(shè)數(shù)組的長度為n，那么以它的每個元素的下標i（i從0開始）為子數(shù)組起點，都有n-i個子數(shù)組，所以所有的子數(shù)組個數(shù)是
   n+n-1+n-2+n-3+…+4+3+2+1
   =(n+1)+(n-1+2)+(n-2+3)+...
   =(n/2)(n+1)
   所以時間復(fù)雜度為O（n2）；
2. 動態(tài)規(guī)劃（復(fù)雜度為O(n)）。對于數(shù)組中第i個元素來說，設(shè)curSum為nums[i]之前的累加和最大值，如果這個最大值<0，那么加上nums[i]之后必然會使累加和變小。即curSum+nums[i]<nums[i]，所以此時應(yīng)該丟掉之前的累加和，從nums[i]重新開始累加。反之，curSum+nums[i]>nums[i]，必定會使和變大（即便nums[i]為負數(shù)）。這樣，每循環(huán)一個元素，都能保證去掉拖后腿的累加和。只要不拖后腿，能多加一個正數(shù)，肯定是有利于累加和的增大。從這些累加中比較出值大的累加和即可。

public static int maxSubArray(int[] nums){
        int curSum = nums[0];//curSum為nums[i]之前的累加和最大值
        int maxSum = nums[0];//最大累加和
        int curBegin = 0;//當(dāng)前累加和起點
        int maxBegin = 0;//最大累加和起點
        int maxEnd = 0;//最大累加和終點
        for(int i=1;i<nums.length;i++){
            if(curSum>0){
                //如果之前的累加和>0，加上nums[i]元素
                curSum += nums[i];
            }else{
                //否則，以nums[i]為起點重新開始
                curSum = nums[i];
                curBegin = i;
            }
            //如果當(dāng)前累加和>記錄的累加和，賦值。并將當(dāng)前累加和的起終點記錄下來
            if(curSum > maxSum){
                maxSum = curSum;
                maxBegin = curBegin;
                maxEnd = i;
            }
        }
        System.out.println("起點:"+maxBegin+",終點:"+maxEnd);
        return maxSum;
    }