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

    前幾天去面試的時候，有家公司好奇怪進行機試，然后我就見到這道題，然后我當時好像做了一天了才做出來。中途的時候好像到2點多的時候以為做出來了。然后給了一組數(shù)據(jù)給我，然后發(fā)現(xiàn)有兩組數(shù)據(jù)是異常的，然后就打斷點在那里跟后來改了一些東西之后發(fā)先運行時報錯和那個死循環(huán)，后來想到另外一種相似的思路，把之前的代碼都注析掉了然后再來寫，到7點鐘的時候寫完，但是調試還是出現(xiàn)運行時錯誤和死循環(huán)，到8點左右把程序調通，我想拍照回去研究研究的時候被拒絕了說公司規(guī)矩，然后我覺得那么短的題目很容易就能記住，回來進行構思另外一種寫法然后寫出來了，結果速度很慢一個21長度的數(shù)組要幾秒鐘才能算出結果，30個長度已經(jīng)看不到停止的時候了。后來昨天有時間研究了下，改進了代碼最終做一個隨機數(shù)組好像能在幾百毫秒算出分組情況吧，然后我又怕忘記之前寫的代碼所以就把這些代碼記下來吧。

#include<vector>
#include<list>
#include<iostream>

using namespace std;

typedef vector<int> intArray_t;

int sumOfArray(const vector<int> &array) {
	int sum = 0;
	int size = array.size();
	for (int i = 0; i < size; i++) {
		sum += array.at(i);
	}
	return sum;
}

bool maxDivFun(list<int> &array, vector<intArray_t> &result, int groupSize, int preSize, vector<int> &preArray, list<int>::iterator iter) {
	while (iter != array.end()) {
		if ((preSize + *iter) <= groupSize) {
			preArray.push_back(*iter);
			bool isFirst = false;
			if (iter == array.begin()) {
				isFirst = true;
			}
			array.erase(iter++);
			if ((preSize + preArray.back()) == groupSize) {
				if (array.empty()) {
					result.push_back(preArray);
					return true;
				}
				else {

					
					list<int> retList(array.begin(), array.end());
					vector<int> grpArray(1, retList.back());
					retList.pop_back();
					if (maxDivFun(retList, result, groupSize, grpArray.at(0), grpArray, retList.begin())) {
						result.push_back(preArray);
						return true;
					}
					
					if (!isFirst)
						iter--;
				}
			}
			else if (isFirst) {
				if (maxDivFun(array, result, groupSize, preSize + preArray.back(), preArray, iter))
					return true;
			}
			else if (maxDivFun(array, result, groupSize, preSize + preArray.back(), preArray, iter--))
				return true;
			if (isFirst) {
				iter = array.begin();
				array.insert(iter, preArray.back());
			}
			else
				array.insert(++iter, preArray.back());
			preArray.pop_back();
		}
		else
			break;
	}
	return false;
}

void maxDiv(const vector<int> &array, vector<intArray_t> &result) {
	if (array.empty())
		return;
	list<int> retList(array.begin(), array.end());
	retList.sort();
	int maxNum = retList.back();
	vector<int> preArray(1, maxNum);
	if (retList.size() == 1) {
		result.push_back(preArray);
		return;
	}
	retList.pop_back();
	int sum = sumOfArray(array);
	if (sum % maxNum == 0) {
		result.push_back(preArray);
		int n = 0;
		while (retList.back() == maxNum) {
			result.push_back(preArray);
			retList.pop_back();
			if (retList.empty())
				return;
			n++;
		}
		preArray.at(0) = retList.back();
		retList.pop_back();
		if (maxDivFun(retList, result, maxNum, preArray.at(0), preArray, retList.begin())) {
			return;
		}
		retList.push_back(preArray.at(0));
		for (; n != 0; n--) {
			retList.push_back(maxNum);
		}
		preArray.at(0) = maxNum;
		result.clear();
	}
	for (int i = maxNum + 1; i <= sum; i++) {
		if (sum % i == 0 && maxDivFun(retList, result, i, preArray.at(0), preArray, retList.begin())) {
			break;
		}
	}
}

    然后我的測試代碼很簡單跑完下面這段程序我的電腦要兩秒多的時間吧。

int main() {
	int a[10000];
	//int a[] = { 1, 2, 4, 5, 100 };
	//int a[] = { 1, 1, 1, 1, 1, 1 };
	//int a[] = { 3, 3, 4, 6, 2 };
	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++) {
		a[i] = i + 1;
	//	while ((a[i] = (rand() % 1000)) == 0);
	}
	vector<int> array(a, a + (sizeof(a)/sizeof(int)));
	vector<intArray_t> result;
	maxDiv(array, result);
	cout << "{";
	int resultSize = result.size();
	for (int i = 0; i < resultSize; i++) {
		if (i != 0)
			cout << ", ";
		cout << "{";
		vector<int> group = result.at(i);
		int groupSize = group.size();
		for (int j = 0; j < groupSize; j++) {
			if (j != 0)
				cout << ", ";
			cout << group.at(j);
		}
		cout << "}";
	}
	cout << "}";
	cout << "\n";
	cout << "The max group num that can divide to have same sum group is: " << resultSize;
	return 0;
}

    但是我又想了很久，一種改進的方法的雛形已經(jīng)出現(xiàn)在我的腦海中，有時間再改，到時候調試沒問題的話也放上來。