一个整数数组，长度为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
上面是别人的分析，我想很多人跟我一样看了相当晕，但看了我的代码你应该不至于晕。有时候用文字表达还真是繁琐，但是代码却简单明了。
大家都说算法和数据结构对程序员来说很重要，还说比的就是这个，我看未必，我觉得更重要的还是分析问题的能力，你要是能把问题分析得相当透彻，我相信你也能写出相应的代码。
很多问题看起来复杂，但是等你分析清楚了，还是相当简单的。这道算法面试题的代码是相当简单啊！
源代码 #include
using namespace 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=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;ij;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; } } } };
排序用了两种方实现。插入排序和选择排序就不多说了，大家都懂。
我要说的是用数组实现排序和用指针实现排序，个人认为指针排序速度要比数组排序快（没有测试），
指针直接访问元素的地址，而数组要先计算元素的偏移，才能得出元素的地址
延伸阅读
最新评论