最大子數組二

上次寫了個算法導論的實現方法，然後繼續看練習題發現可以用更簡單的方式去實現，利用線性的方式去實現O(n)復雜度的算法。思想是記錄從左邊記錄自己當前處理過的最大子數組，然後進行連續記錄，如果加和小於0，則置為0，繼續進行加和求解！

具體代碼如下：

[cpp]
int Find_MaxiMum_SubArray2(int *A,int low,int high,int& max_left,int& max_right,int& max_value) 
{ 
    max_left = low; 
    max_right= low; 
 
    max_value  = 0; 
 
    int ThisSum=0; 
    int tmp_left=low; 
    for (int i = low; i < high+1; i++) 
    { 
        ThisSum += A[i]; 
        if (ThisSum>max_value) 
        { 
            max_value = ThisSum; 
            max_right = i; 
            max_left = tmp_left; 
        } 
        else if(ThisSum<0) 
        { 
            ThisSum = 0; 
            tmp_left = i+1; 
        } 
 
    } 
 
    return 0; 
} 

int Find_MaxiMum_SubArray2(int *A,int low,int high,int& max_left,int& max_right,int& max_value)
{
 max_left = low;
 max_right= low;

 max_value  = 0;

 int ThisSum=0;
 int tmp_left=low;
 for (int i = low; i < high+1; i++)
 {
  ThisSum += A[i];
  if (ThisSum>max_value)
  {
   max_value = ThisSum;
   max_right = i;
   max_left = tmp_left;
  }
  else if(ThisSum<0)
  {
   ThisSum = 0;
   tmp_left = i+1;
  }

 }

 return 0;
}
發現代碼比原來更短，且時間復雜度更好。