一道算法题，看看大家的思路

题目描述：有31，-41，59，26，-53，58，97，-93，-23，84十个数。SUM（N，M）表示从第N个数到到第M个数的和。例如：SUM（2，3）=-41+59=18。问：最大的和是多少？对应的N和M是多少？

　　这个题目并不难，实现的方法多种多样。最坏的算法，遍历所有的情况，求出最大和。

　　我在这儿提一个算法的思路，不是最优的，主要是讲解这个算法的。

　　模拟生物算法（谢谢装配脑袋指正，这应该是遗传算法）。

　　根据题目，构造生物S，生物S有三个属性N、M、V。N表示开始的下标，M表示结束的下标，和题目中的定义一样。V表示从第N个数到第M个数的和，V和N、M是相关的。因此，可以用S（N，M）表示这个生物。

　　先期构造10个这样的生物。称为第一代。

　　生物有两个特性，繁衍性和变异性。

　　繁衍性：生物S1（N1，M1）和生物S2（N2，M2）繁衍的后代为生物S3（N1，M2）和生物S4（N2，M1）

　　变异性：生物S1（N1，M1）产生变异，得到S2（N2，M1）或者是S2（N1，M2）

　　第一代生物通过繁衍和变异得到10个后代（繁衍和变异的比例自定）。这样一共有20个生物。然后这20个生物采用优胜劣汰的方法，保留10个V最大的生物，淘汰10个生物。这称为自然选择的一代。

　　模拟大自然的自然选择，通过初期的10个生物，经过5代的自然选择，基本上就能得到最优解。

　　模拟生物算法（遗传算法），就是利用繁衍和变异以及优胜劣汰，保留最优的生物，得到最优解。在某些实际问题中，能达到不错的效果。不过模拟生物算法（遗传算法）不能保证一定能在最优解收敛，但基本上能保证在局部最优解上实现收敛。

　　本题用模拟生物算法（遗传算法）并不是最合适，我只是利用这道题简单介绍模拟生物算法的基本思想。

　　欢迎各位提出本题的最优算法，空间上的最优算法、时间上的最优算法。

  本文转自万仓一黍博客园博客，原文链接：http://www.cnblogs.com/grenet/archive/2010/01/27/1657501.html，如需转载请自行联系原作者