連續向量最大和（一維模式識别）算法的分析與優化

輸入：n個互相沒有關聯的數字（正負随機）

輸出：該數組中連續數字的最大和

    如在數組3 -4 5 2 -5 5 9 -9 -2 8中，連續數字最大和為5 2 -5 5 9這個數字序列的和，最大和為16

一、簡單疊代算法

    遇到這種問題，頭腦中冒出的最直接最簡單的就是這種算法。用一個雙重循環，一個代表起始位置，一個标注末尾，計算其中元素的和，在與最大值比較，得出新的最大值。

1. for(int i = 0;i<N;i++)  
2.     {  
3.         int sum = 0;  
4.         for(int j = i;j<N;j++)  
5.         {  
6.             sum += arr[j];  
7.             max = MAX(sum,max);  
8.         }  

9.     }

   對于輸入規模n來說，該解法會執行n^2步，是以該算法為平方時間。

二、動态規劃的疊代算法

    我們可以用一個數組sum[i]，代表前i個整數和這樣一種狀态。是以後一個狀态就由前一個狀态加arr[i]得到，而兩個狀态相減則得到了兩個整數中間數的和。

1. for(int i = 1;i<N;i++)  
2.     sum[i] = sum[i-1]+arr[i];  
3. for(int i = N-1;i>=0;i--)  
4.     for(int j = i;j>=0;j--)  
6.         int sum1 = sum[i] - sum[j];  
7.         max = MAX(max,sum1);  

8.     }  

   對于輸入規模n來說，該解法會執行n^2步，是以該算法仍然為平方時間。

三、分治算法

    将一個數組的最大和問題轉換為兩個數組的最大和問題，然後遞歸的找出兩個向量的最大和。不過要考慮一種情況就是和最大的那一組數組可能跨越兩個子數組的邊界，是以需要對邊界的數組進行處理。對于跨越邊界的問題，分别在兩個數組中從邊界開始，計算邊界的最大和，再将兩個邊界最大和相加，與子數組的最大和比較。

1. float maxsum3(int l,int u)  
2. {  
3.     if(l>u)  
4.         return 0;  
5.     if(l == u)  
6.         return MAX(0,arr[l]);  
7.     int m = (l+u)/2;  
8.     int lmax = 0,sum = 0;  
9.     for(int i = m;i>=l;i--)  
11.         sum += arr[i];  
12.         lmax = MAX(lmax,sum);  
14.     int rmax = 0;  
15.     sum = 0;  
16.     for(int i = m+1;i<=u;i++)  
19.         rmax = MAX(rmax,sum);  
21.     return max((float)lmax+rmax,maxsum3(l,m),maxsum3(m+1,u));  

22. }  

    可以看到子數組求值的方向都是從邊界(中間)向兩邊展開的。

    該算法每次執行n次操作，遞歸總共有log n次，是以時間複雜度為O(n lon n)。

四、掃描算法

    在這個問題中，正負數随機出現，是以我們預設在一個較長的數組裡，最大和是大于零的。對一個元素不多的數組進行直覺運算時，我們總是習慣于從左往右開始掃描數字，當發現幾個數字的和小于0時就直接略過前面的數字，從新位置開始掃描，并記錄下出現過的最大值，直到掃描完整個數組。1977年，當這個問題（模式比對）被布朗大學的Grenander提出時，他獨立設計出了兩個平方算法。後來他将問題講給Michael Shamos聽，後者提出了分治算法。那時，他們倆都認為沒有更好的算法了，直到後來Michael Shamos在卡耐基——梅隆大學的一次研讨會上提起了這個問題，而參會的一個統計學家Jay Kadane在一分鐘内就設計除了線性時間的掃描算法。不過這下，應該不會再有更優的算法了，畢竟任何算法都至少要花費O(n)的時間。

1. int maxsofar = 0,maxendinghere = 0;  
4.     maxendinghere = MAX(maxendinghere+arr[i],0);  
5. printf("%d %d",i,maxendinghere);   
6.     maxsofar = MAX(maxsofar,maxendinghere);  
7. printf(" %d\n",maxsofar);  

9. printf("%d",maxsofar);  

   對于{3,-4,2,5,-5,5,9,-9,-2,8}這個數組，過程是這樣的：

    線性時間的算法，效率嘛，誰用誰知道。

注：四個算法的代碼在 最大和詳細代碼