32 lines
712 B
Text
32 lines
712 B
Text
local function gss(s)
|
|
local best = 0
|
|
local start = 1
|
|
local finish = 1
|
|
local sum = 0
|
|
local sum_start = 1
|
|
for i, x in s do
|
|
sum += x
|
|
if sum > best then
|
|
best = sum
|
|
start = sum_start
|
|
finish = i + 1
|
|
elseif sum < 0 then
|
|
sum = 0
|
|
sum_start = i + 1
|
|
end
|
|
end
|
|
return s:slice(start, finish - 1), best
|
|
end
|
|
|
|
local tests = {
|
|
{-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1},
|
|
{-1, 1, 2, -5, -6},
|
|
{},
|
|
{-1, -2, -1}
|
|
}
|
|
for tests as test do
|
|
print($"Input: \{{test:concat(", ")}}")
|
|
local subseq, sum = gss(test)
|
|
print($"Sub seq: \{{subseq:concat(", ")}}")
|
|
print($"Sum: {sum}\n")
|
|
end
|