求數組最大子數組

   題目：輸入一個整形數組，數組裡有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間複雜度為O(n)。
   例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，是以輸出為該子數組的和18。      

Solution1：時間複雜度為O(n)

      思想：1)假設數組至少含有一個正數。對數組周遊。初始化low=high=0，preSum=max=0;                         如果目前的和preSum為負數，preSum應該重置為0，标記low=high=i+1;                         如果目前的和preSum>max，則max=preSum，且high=i                  2)倘若max==0，說明數組全是負，則尋找最大元素data[i]即可，且low=high=i;                  3)傳回low,high,max                  4)數組最多線性周遊2遍，故時間複雜度為O(n)

void find(int data[],int length,int&low,int&high,int&max){

	int preSum=0;
	max=low=high=0;
	for(int i=0;i<length;i++){
		preSum+=data[i];
		if(preSum<0){//目前和為負數，清空
			preSum=0;
			low=high=i+1;
		}
		else if(preSum>max){//目前和大于最大和，交換并記錄結束位置
			max=preSum;
			high=i;
		}
	}

	if(max==0){//全是負數，尋找最大負數即可
		max=data[0];
		for(int i=1;i<length;i++ ){
			if(max<data[i]){
			    max=data[i];
			    low=high=i;
			}
		}
	}
}
           

Solution2：時間複雜度為O(nlogn)

             思想：使用了分塊和遞歸法。假設目前需要尋找的最大子數組的索引段為[low,high]。取中間位置mid,那麼最大子數組存在可能性有3種情況，第1種是位于[low mid-1]中：第2種是位于[mid+1 high]中；第3種必須包含mid，即以mid為基礎，向兩邊延伸，這需要線性時間查找。對于1、2種情況，遞歸即可。              比較3種情況最大的，即為結果。

struct r{
     int low,high;
     int sum;
	 r(int l,int h,int s=0):low(l),high(h),sum(s){}
 };
 
 r find(int data[],int n,int low,int high){
 
      if(low==high)
	      return r(low,high,data[low]);
      else if(high==low+1){
	     r left(low,low,data[low]);
	     r right(high,high,data[high]);
	     r middle(low,high,data[low]+data[high]);
	     r temp=left.sum>right.sum? left:right;
	     return temp.sum>middle.sum?temp:middle;
	   }
      else{
	    int mid=(low+high)/2;
            r left=find(data,n,low,mid-1);
	    r righ=find(data,n,mid+1,high);
	    r temp=left.sum>righ.sum? left:righ;
			
	    int maxLeft,maxRight,sum;
	    int p1=mid;
            maxLeft=data[mid];
	    sum=data[mid];
	    for(int i=mid-1;i>=low;i--){
		sum+=data[i];
	        if(sum>maxLeft){
		   p1=i;
	          maxLeft=sum;
	        }
	   }

	    int p2=mid;
            maxRight=0;
	    sum=0;
	    for(int i=mid+1;i<=high;i++){
		sum+=data[i];
		if(sum>maxRight){
		   p2=i;
		   maxRight=sum;
		}
	    }

	     r middle(p1,p2,maxLeft+maxRight);
	     return temp.sum>middle.sum?temp:middle;
	   }
 }
           

Solution3：時間複雜度為O(n.^2)

     思想：設目前索引[0 i]資料段（i<=lenght-1）具有最大Max的子數組的低高索引分别為 low，high，對應的累加值為MAX。則，尋找索引[0 i+1]這段區間的最大子數組的時候，有以下兩種情況：

     1.仍舊為low-high
     2.為flag---i+1，其中0<=flag<=i+1。      

            那麼對第2中情況從後往前累加，找出最大的累加值max和記錄對應的位置flag，比較max與MAX，若大則更新MAX=max,low=flag,high=i+1。

SubArray FindMaxSubArray(int data[],int length)//非遞歸法計算最大子數組  
{  
    int max=data[0];  
    int low=0,high=0;//初始化  
    for(int i=1;i<length;i++)  
        {int present_sum=data[i],present_max=data[i];  
         int label=i;  
          for(int j=i-1;j>-1;j--)  
              {present_sum+=data[j];  
               if(present_max<present_sum)  
                  {present_max=present_sum;label=j;}}  
          if(present_max>max)  
               {max=present_max;low=label;high=i;}    
         }  
    SubArray maxarray={low,high,max};  
    return max
}