算法--将數組分成和相等的多個子數組，求子數組的最大個數

一個整數數組，長度為n，将其分為m份，使各份的和相等，求m的最大值

  比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1; 

  {3,6}{2,4,3} m=2

  {3,3}{2,4}{6} m=3 是以m的最大值為3

算法 原理的思想是将大問題轉換成小問題。

就{3，2，4，3，6}的操作步驟：

      第一步：想将數組遞減排序得{6，4，3，3，2}，求出數組中所有數的和m=18,第一個最大的數b=6， m/b=3餘數為0，

當除數為1，餘數為0時終止。當餘數不為0時，轉到第三步。當餘數為0時将數組劃分為{6}，{4，3，3，2}兩個。把{4，3，3，2}看成一個新的數組。

      第二步：先用{4，3，3，2}中的最大數與b=6比較，即4<b，是以再将4與最右邊的數即2相加與b比較，

結果相等，則将這兩個數從該數組中除去生成新的數組，轉到第一步，現在的結果是{6},{4,2},{3,3},把{3,3}看成一個新的數組繼續重複第二步。

      第三步，将數組中最大的數與最小的數取出構成一個新數組Z，剩餘的構成一個數組，然後，

判斷m/Z中數字之和看是否餘數為0，若為0，把b替換為Z中數字之和轉第二步，若不為0，

繼續從剩餘的數字中取出最小值加入到Z中，再判斷m/Z中數字之和看是否餘數為0，直到為0，轉第二步為止。

最後得到的結果是{6},{4,2},{3,3} 這時可以計算出m為3，也可以在程式中作記載。

在第二步工程過，若出現兩個數相加大于上一次的b，則将程式轉到第三步。

上面是别人的分析，我想很多人跟我一樣看了相當暈，但看了我的代碼你應該不至于暈。有時候用文字表達還真是繁瑣，但是代碼卻簡單明了。

大家都說算法和資料結構對程式員來說很重要，還說比的就是這個，我看未必，我覺得更重要的還是分析問題的能力，你要是能把問題分析得相當透徹，我相信你也能寫出相應的代碼。

很多問題看起來複雜，但是等你分析清楚了，還是相當簡單的。這道算法面試題的代碼是相當簡單啊！

<a></a>

#include&lt;iostream&gt;

usingnamespace std ;

class FindMaxM

{

public: 

int FindM(int arr[],int length)

if(NULL==arr || length&lt;=0)

return-1;

}

//倒序排序

InsertSort(arr,length);

int sum=0;//數組的和

for(int i=0;i&lt;length;i++)

sum+=arr[i];

int end=length-1;

int subSum=arr[0];

while(sum/subSum&gt;=2)

if(sum%subSum==0)

return sum/subSum;

subSum+=arr[end--];

private :

//用數組實作插入排序

inline void InsertSort(int arr[],int length)

int cur;

for(int i=1;i&lt;length;i++)

cur=arr[i];

for(int j=0;j&lt;i;j++)

if(arr[j]&lt;cur)

for(int k=i;k&gt;j;k--)

arr[k]=arr[k-1];

arr[j]=cur;

break;

//用指針實作選擇排序

inline void SelectSort(int* ptArr, int n)

for (int i =0; i &lt; n -1; i++)

int k =i;

for (int j = i +1; j &lt; n; j++)

if (*(ptArr+ j) &gt;*(ptArr+ k))

k = j;

if (k != i)

int tmp =*(ptArr+ k);

*(ptArr+ k) =*(ptArr+ i);

*(ptArr+ i) = tmp;

};

排序用了兩種方實作。插入排序和選擇排序就不多說了，大家都懂。

我要說的是用數組實作排序和用指針實作排序，個人認為指針排序速度要比數組排序快（沒有測試），

指針直接通路元素的位址，而數組要先計算元素的偏移，才能得出元素的位址

本文轉自啊漢部落格園部落格，原文連結：http://www.cnblogs.com/hlxs/archive/2011/06/26/2090586.html