【微软谷歌面试100题--【45】一个整数数组，长度为n，将其分为m 份，使各份的和相等，求m 的最大值

第45题

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

既然是各份的和相等，首先让我们想到的是，先对这个数组求和，然后去求解一个分组的个数问题。

然后 定义变量 i=length（数组长度），i>0，i--，去寻找满足的最大的 i

import java.util.ArrayList;
import java.util.List;
public class Algorithm45_0 {
	static int getMax(int a[]){
		int sum=0;
		List<Integer> myList=new ArrayList<Integer>();
		for(int aa:a){
			sum+=aa;
			myList.add(aa);
		}
		for(int i=a.length;i>0;i--){
			if(sum%i==0){
				if(ifExsits(myList,sum/i,sum/i)){
					return i;
				}
			}
		}
		return 1;
	}
	
	static boolean ifExsits(List<Integer> rootList,int num,int orgNum){
		if(rootList.size()==0&&num==orgNum){
			return true;
		}
		boolean flag=false;
		for(int i=0;i<rootList.size();i++){
			List<Integer> subList=new ArrayList<Integer>();
			for(int j=0;j<rootList.size();j++){
				if(j!=i){
					subList.add(rootList.get(j));
				}
			}
			if(rootList.get(i)==num){
				flag=flag||ifExsits(subList, orgNum, orgNum);
			}else if(rootList.get(i)<num){
				flag=flag||ifExsits(subList, num-rootList.get(i), orgNum);
			}
		}
		return flag;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]={1,2,3,6,6};
		int b=getMax(a);
		System.err.println(b);
	}
}