egamesir blog

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

上代码：

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