/**
  * 方法1（蠻力法）：兩次循環(huán)求最大子數(shù)組之和
  */
 public static int maxSubArray1(int[] a){
  int i,j;
  int ThisSum=0;
  int MaxSum=0;
  for (i = 0; i < a.length; i++) {
   ThisSum=a[i];
   for(j=i+1;j<a.length;j++){
    ThisSum+=a[j];
    if(ThisSum>MaxSum){
     MaxSum=ThisSum;
    }
   }
  }
  return MaxSum;
 }

/**
  * 方法2：優(yōu)化的動態(tài)規(guī)劃方法
  * nEnd就是通過“數(shù)組依次相加加到a[i]，然后與a[i]做比較”得來的，保存較大的。因為如果前面的數(shù)加到a[i]
  * 還沒有a[i]本身大，那么前面的數(shù)也就對最大子數(shù)組和沒有貢獻(xiàn)。厲害
  * nAll就是記錄一下之前的新得到的nEnd和自身之前誰更大
  */
 public static int max(int m,int n){
  return m>n?m:n;
 }
 public static int maxSubArray2(int[] a){
  int nAll=a[0];//有n個數(shù)字?jǐn)?shù)組的最大子數(shù)組之和
  int nEnd=a[0];//有n個數(shù)字?jǐn)?shù)組包含最后一個元素的子數(shù)組的最大和
  for (int i = 1; i < a.length; i++) {
   nEnd=max(nEnd+a[i],a[i]);
   nAll=max(nEnd, nAll);
  }
  return nAll;
 }
 private static int begin=0;
 private static int end=0;
 /**
  * 求出最大子數(shù)組的開始begin，結(jié)尾end，以及整個子數(shù)組
  */
 public static int maxSubArray3(int[] a){
  int maxSum=Integer.MIN_VALUE;
  int nSum=0;
  int nStart=0;
  for (int i = 0; i < a.length; i++) {
   if(nSum<0){
    nSum=a[i];
    nStart=i;
   }
   else{
    nSum+=a[i];
   }
   if(nSum>maxSum){
    maxSum=nSum;
    begin=nStart;
    end=i;
   }
  }
  return maxSum;
 }