算法好玩，我不会编程，就让我用找一种算法来口算那些数学问题吧

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4922 天前的主题，其中的信息可能已经有所发展或是发生改变。

闲来无聊，搜索“算法题”，结果如下（原文 http://www.cnblogs.com/grenet/archive/2010/02/21/1670208.html ）：

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

首先，我自己空中楼阁的想法：

因为是次第的加，所以 N 与 M 分开考虑。
首先判断第M+1个数是否为正数，为正数则M=M+1。若不为正数则继续向后看，第M+2个数是否为正数，如果为正数，就判断这两个数加起来是否为正数，为正数则M=M+2。以此类推，算出M最大值。
设一个递增的非负整数Y，且Y<M+1，并判断第N+Y个数是否为正数，若为正数，则N=N。若第N+Y个数为负数，则计算SUM（N，N+Y）是否为正数，若为正数，则Y继续递增，若为负数，则N=N+Y+1，Y归最小，继续判断。
M与N的计算都是从1开始的。

口算答案：M=7，N=3

后来我发现自己判断了很多次，对人来说，思考是很简单的，但对于写成编程语言就……我想我的思考方式还是“计算人”，而不是“计算机”吧。

正数

个数

SUM

10 条回复 • 1970-01-01 08:00:00 +08:00

forwap

2011-06-14 14:03:36 +08:00

- -!直接心算出来,不到1分钟(当然这个比较简单)

darktiny

2011-06-14 14:20:39 +08:00

楼主的bio很有意思

ssword

2011-06-14 14:31:35 +08:00

这种题目小学水平。建议楼主搜下project euler

kernel31

2011-06-14 14:42:17 +08:00

没看懂lz的算法，我自己想了一个，首先想像这个数列的前n项和S(n)。SUM(N,M)=S(M)-S(N-1)。要使SUM(N,M)最大，N,M必须满足对任何n<N，S(n)>=S(N-1)；对任何n>M，S(n)<=S(M)。这是使SUM(N,M)最大必要条件而非充分条件，可能有不只一对N,M满足上面的条件，只需要找出这些N,M对并选出其中和最大的一对就可以

CoX

2011-06-14 15:15:25 +08:00

到实际应用的时候，肯定就不是十个数这么简单了

iugo

2011-06-14 18:59:20 +08:00

@CoX 的确，所以需要计算机。程序员就是作文者+翻译，设计了，还要翻译给机器听。

@kernel31 嗯，我想我基本看懂您的意思了。我想您是真的在写算法，而我只是当做数学题。

@ssword 咕~~(╯﹏╰) 到达目的地很简单，只是寻找不同的路去走，看哪条路上风景比较好看。

@darktiny 呵呵，配合我这个头像。 @Livid 说过V2EX不欢迎没有头像的人，然后我就在想这个问题：头像是一种基本的个人特征，但是头像是可以换的，可能只是代表一个人某时刻心情的，但ID就不一样了。

@forwap 我心算不行，至今还未看过任何心算方面的书籍。

chloerei

2011-06-14 19:26:36 +08:00

我只懂得穷举

tioover

2011-06-14 19:59:41 +08:00

《离散数学及其应用》在书架上吃灰的路过

dementrock

2011-06-15 05:52:30 +08:00 via iPhone

经典的动态规划问题最大子段和问题

cmonday

2011-06-15 08:44:56 +08:00

算法！上了大学之后就没搞过算法了，都快忘完了……
LZ的算法好纠结，感觉效率很低的样子，我理一下这个题……

用A[n]表示前n个数的集合，a[n]表示第n个数，也就是说：
A[n]={a[1],a[2],...,a[n]}
那么A[n]的最大子段一定是A[1],A[2],...,A[n-1],A[n]的最大子段中间的一个
唔，上面那句话是一句彻头彻尾的废话
由于A[1],A[2],...,A[n-1],A[n]都是A[n]的前接子段（以a[1]开头），那么

A[n]的最大子段一定是A[1],A[2],...,A[n-1],A[n]的最大后接子段中间的一个

用b[n]来表示A[n]的最大后接子段，那么
如果(b[n-1]>0)，则b[n]=b[n-1]+a[n]
如果(b[n-1]<0)，则b[n]=a[n]
如果(b[n-1]==0)，则上面的两个式子的值相等，也就是说，此题也许有多个最优解

按照上述思路，先算b[1]，再依此计算b[2],b[3],...,b[n]，并在过程中记录最大的子段及其对应的M,N即可

如此这般……应该没错吧，擦汗。真的离开这个太久了。