Skip to content

Commit fe6d8e2

Browse files
YonabaYonaba
committed
Added Brute-force algorithm
1 parent cc9b0a8 commit fe6d8e2

4 files changed

Lines changed: 87 additions & 62 deletions

File tree

‎Maximum_Subarray/Lua/Yonaba/kadanes.lua‎

Lines changed: 0 additions & 28 deletions
This file was deleted.

‎Maximum_Subarray/Lua/Yonaba/kadanes_test.lua‎

Lines changed: 0 additions & 34 deletions
This file was deleted.

‎Maximum_Subarray/Lua/Yonaba/maximum_subarray.lua‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
-- Greatest subsequential sum finding algorithms implementation
2+
-- See: http://en.wikipedia.org/wiki/Maximum_subarray_problem
3+
4+
-- Computes the largest sub-sequential sum using kadanes algorithm
5+
-- s : a given sequence
6+
-- returns : the sum of the largest subsequence found
7+
-- returns : the starting index of the largest subsequence found
8+
-- returns : the final index of the largest subsequence found
9+
local function kadanes(s)
10+
local n = #s
11+
if n< 1 then return 0 end
12+
local max_ending_here, max_so_far = s[1], s[1]
13+
local begin, begin_tmp, last = 1, 1, 1
14+
for i = 2, n do
15+
if max_ending_here < 0 then
16+
max_ending_here = s[i]
17+
begin_tmp = i
18+
else
19+
max_ending_here = max_ending_here + s[i]
20+
end
21+
if max_ending_here >= max_so_far then
22+
max_so_far = max_ending_here
23+
begin = begin_tmp
24+
last = i
25+
end
26+
end
27+
return max_so_far, begin, last
28+
end
29+
30+
-- Computes the largest sub-sequential sum using a brute-force algorithm
31+
-- s : a given sequence
32+
-- returns : the sum of the largest subsequence found
33+
-- returns : the starting index of the largest subsequence found
34+
-- returns : the final index of the largest subsequence found
35+
local function gss_brute_force(s)
36+
local st, ed = 1
37+
local sum , max = s[st], s[st]
38+
for i = 1, #s do
39+
for j = i, #s do
40+
sum = 0
41+
for k = i, j do sum = sum + s[k] end
42+
if sum > max then
43+
st, ed = i, j
44+
max = sum
45+
end
46+
end
47+
end
48+
return max, st, ed==nil and st or ed
49+
end
50+
51+
return {
52+
kadanes = kadanes,
53+
brute_force = gss_brute_force,
54+
}

‎Maximum_Subarray/Lua/Yonaba/maximum_subarray_test.lua‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
-- Tests for maximum_subarray.lua
2+
local gss = require 'maximum_subarray'
3+
4+
local total, pass = 0, 0
5+
6+
local function dec(str, len)
7+
return #str < len
8+
and str .. (('.'):rep(len-#str))
9+
or str:sub(1,len)
10+
end
11+
12+
local function run(message, f)
13+
total = total + 1
14+
local ok, err = pcall(f)
15+
if ok then pass = pass + 1 end
16+
local status = ok and 'PASSED' or 'FAILED'
17+
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
18+
end
19+
20+
run('Kadanes algorithm', function()
21+
local max, i, j = gss.kadanes {1, 2, 3, 4, 5}
22+
assert( max == 15 and i == 1 and j == 5)
23+
24+
local max, i, j = gss.kadanes {-1, -2, -3, -4, -5}
25+
assert( max == -1 and i == 1 and j == 1)
26+
27+
local max, i, j = gss.kadanes {-2, 1, -3, 4, -1, 2, 1, -5, 4}
28+
assert( max == 6 and i == 4 and j == 7)
29+
end)
30+
31+
print(('-'):rep(80))
32+
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
33+
:format(total, pass, total-pass, (pass*100/total)))

0 commit comments

Comments
 (0)