最大子序列和

egamesir posted @ 2011年10月25日 11:54 in lua with tags Lua Algorithm , 2155 阅读

算法方面一直是弱项，一直没有去锻炼过。今天看到is-Programmer上有人说到子序列和，也回顾了一下。用lua实现了复杂度为O(n)的动态规划法求最大序列和算法，支持全负序列。没啥技术含量，权当练习lua和熟悉算法了。

上代码：

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ta = {1,-2,-3,5,2,-5,7,2,-1,2,-2}
  
function asm(t)
    local maxn,currn=t[1],1
    local left,right=1,1
  
    for i=1,#t do
        currn = currn+t[i]
        if currn > maxn then
            maxn = currn
            right = i
        else
            if currn < 0 then
                currn = 0
                left = i + 1
            end
        end
    end
 
    print(maxn,unpack(t,left,right))
end
 
-- 输出结果:
Lua 5.1.4  Copyright (C) 1994-2008 Lua.org, PUC-Rio
> 12 5 2 -5 7 2 -1 2
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter