算法--将数组分成和相等的多个子数组，求子数组的最大个数

一个整数数组，长度为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