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

作者：陳太漢

一個整數數組，長度為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}看成一個新的數組繼續(xù)重復第二步。
      第三步，將數組中最大的數與最小的數取出構成一個新數組Z，剩余的構成一個數組，然后，
判斷m/Z中數字之和看是否余數為0，若為0，把b替換為Z中數字之和轉第二步，若不為0，
繼續(xù)從剩余的數字中取出最小值加入到Z中，再判斷m/Z中數字之和看是否余數為0，直到為0，轉第二步為止。
最后得到的結果是{6},{4,2},{3,3} 這時可以計算出m為3，也可以在程序中作記載。
在第二步工程過，若出現兩個數相加大于上一次的b，則將程序轉到第三步。

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

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

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

源代碼

#include<iostream>
usingnamespace std ;

class FindMaxM
{
public:
int FindM(int arr[],int length)
{
if(NULL==arr || length<=0)
{
return-1;
}

//倒序排序
InsertSort(arr,length);

int sum=0;//數組的和
for(int i=0;i<length;i++)
{
sum+=arr[i];
}

int end=length-1;
int subSum=arr[0];
while(sum/subSum>=2)
{
if(sum%subSum==0)
{
return sum/subSum;
}
subSum+=arr[end--];
}

return-1;
}

private :
//用數組實現插入排序
inline void InsertSort(int arr[],int length)
{
int cur;
for(int i=1;i<length;i++)
{
cur=arr[i];
for(int j=0;j<i;j++)
{
if(arr[j]<cur)
{
for(int k=i;k>j;k--)
{
arr[k]=arr[k-1];
}
arr[j]=cur;
break;
}
}
}
}

//用指針實現選擇排序
inline void SelectSort(int* ptArr, int n)
{
for (int i =0; i < n -1; i++)
{
int k =i;
for (int j = i +1; j < n; j++)
{
if (*(ptArr+ j) >*(ptArr+ k))
{
k = j;
}
}
if (k != i)
{
int tmp =*(ptArr+ k);
*(ptArr+ k) =*(ptArr+ i);
*(ptArr+ i) = tmp;
}
}
}

};

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

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

指針直接訪問元素的地址，而數組要先計算元素的偏移，才能得出元素的地址