python数组分成两个和相等的⼦集_算法--将数组分成和相等的多个⼦数组，求⼦数组的最⼤。。。
作者：陈太汉
⼀个整数数组，长度为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
结果相等，则将这两个数从该数组中除去⽣成新的数组，转到第⼀步，现在的结果是{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，则将程序转到第三步。
上⾯是别⼈的分析，我想很多⼈跟我⼀样看了相当晕，但看了我的代码你应该不⾄于晕。有时候⽤⽂字表达还真是繁琐，但是代码却简单明了。
⼤家都说算法和数据结构对程序员来说很重要，还说⽐的就是这个，我看未必，我觉得更重要的还是分析问题的能⼒，你要是能把问题分析得相当透彻，我相信你也能写出相应的代码。
很多问题看起来复杂，但是等你分析清楚了，还是相当简单的。这道算法⾯试题的代码是相当简单啊！
源代码
#includeusingnamespacestd ;classFindMaxM
{public:intFindM(intarr[],intlength)
{if(NULL==arr||length<=0)
{return-1;
}//倒序排序InsertSort(arr,length);intsum=0;//数组的和for(inti=0;i
python获取数组长度{
sum+=arr[i];
}intend=length-1;intsubSum=arr[0];while(sum/subSum>=2)
{if(sum%subSum==0)
{returnsum/subSum;
}
subSum+=arr[end--];
}return-1;
}private://⽤数组实现插⼊排序inlinevoidInsertSort(intarr[],intlength)
{intcur;for(inti=1;i
{
cur=arr[i];for(intj=0;j
{if(arr[j]
{for(intk=i;k>j;k--)
{
arr[k]=arr[k-1];
}
arr[j]=cur;break;
}
}
}
}//⽤指针实现选择排序inlinevoidSelectSort(int*ptArr,intn)
{for(inti=0; i
{intk=i;for(intj=i+1; j
{if(*(ptArr+j)>*(ptArr+k))
{
k=j;
}
}if(k!=i)
{inttmp=*(ptArr+k);*(ptArr+k)=*(ptArr+i);*(ptArr+i)=tmp;
}
}
}
};
排序⽤了两种⽅实现。插⼊排序和选择排序就不多说了，⼤家都懂。
我要说的是⽤数组实现排序和⽤指针实现排序，个⼈认为指针排序速度要⽐数组排序快(没有测试)，指针直接访问元素的地址，⽽数组要先计算元素的偏移，才能得出元素的地址

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。