maximum subarray


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Tags

Source Code

-- Greatest subsequential sum finding algorithms implementation
-- See: http://en.wikipedia.org/wiki/Maximum_subarray_problem

-- Computes the largest sub-sequential sum using kadanes algorithm
-- s       : a given sequence
-- returns : the sum of the largest subsequence found
-- returns : the starting index of the largest subsequence found
-- returns : the final index of the largest subsequence found
local function kadanes(s)
  local n = #s
  if n< 1 then return 0 end
  local max_ending_here, max_so_far = s[1], s[1]
  local begin, begin_tmp, last = 1, 1, 1
  for i = 2, n do
    if max_ending_here < 0 then
      max_ending_here = s[i]
      begin_tmp = i
    else
      max_ending_here = max_ending_here + s[i]
    end
    if max_ending_here >= max_so_far then
      max_so_far = max_ending_here
      begin = begin_tmp
      last = i
    end
  end
  return max_so_far, begin, last
end

-- Computes the largest sub-sequential sum using a brute-force algorithm
-- s       : a given sequence
-- returns : the sum of the largest subsequence found
-- returns : the starting index of the largest subsequence found
-- returns : the final index of the largest subsequence found
local function gss_brute_force(s)
  local st, ed = 1
  local sum , max = s[st], s[st]
  for i = 1, #s do
    for j = i, #s do
      sum = 0
      for k = i, j do sum = sum + s[k] end
      if sum > max then
        st, ed = i, j
        max = sum
      end
    end
  end
  return max, st, ed==nil and st or ed
end

-- Computes the largest sub-sequential sum by computing sub-sums
-- s       : a given sequence
-- returns : the sum of the largest subsequence found
-- returns : the starting index of the largest subsequence found
-- returns : the final index of the largest subsequence found
local function gss_subsums(s)
  local st, ed = 1
  local sum , max = s[st], s[st]
  for i = 1, #s do
    sum = 0
    for j = i, #s do
      sum = sum + s[j]
      if sum > max then
        st, ed = i, j
        max = sum
      end
    end
  end
  return max, st, ed==nil and st or ed
end

-- Computes the largest sub-sequential sum with dynamic programming
-- s       : a given sequence
-- returns : the sum of the largest subsequence found
-- returns : the starting index of the largest subsequence found
-- returns : the final index of the largest subsequence found
local function gss_dynamic(a)
  local s, t = {}, {}
  s[1], t[1] = a[1], 1
  local max = s[1]
  local st, ed = 1, 1
  for i = 2, #a do
    if s[i-1] > 0 then
      s[i] = s[i-1] + a[i]
      t[i] = t[i-1]
    else
      s[i] = a[i]
      t[i] = i
    end
    if s[i] > max then
      st, ed = t[i], i
      max = s[i]
    end
  end
  return max, st, ed
end

return {
  kadanes     = kadanes,
  brute_force = gss_brute_force,
  subsums     = gss_subsums,
  dynamic     = gss_dynamic,
}
-- Tests for maximum_subarray.lua
local gss = require 'maximum_subarray'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Kadanes algorithm', function()
  local max, i, j = gss.kadanes {1, 2, 3, 4, 5}
  assert( max == 15 and i == 1 and j == 5)

  max, i, j = gss.kadanes {-1, -2, -3, -4, -5}
  assert( max == -1 and i == 1 and j == 1)

  max, i, j = gss.kadanes {-2, 1, -3, 4, -1, 2, 1, -5, 4}
  assert( max == 6 and i == 4 and j == 7)
end)

run('Brute-force algorithm', function()
  local max, i, j = gss.brute_force {1, 2, 3, 4, 5}
  assert( max == 15 and i == 1 and j == 5)

  max, i, j = gss.brute_force {-1, -2, -3, -4, -5}
  assert( max == -1 and i == 1 and j == 1)

  max, i, j = gss.brute_force {-2, 1, -3, 4, -1, 2, 1, -5, 4}
  assert( max == 6 and i == 4 and j == 7)
end)

run('Subsums', function()
  local max, i, j = gss.subsums {1, 2, 3, 4, 5}
  assert( max == 15 and i == 1 and j == 5)

  max, i, j = gss.subsums {-1, -2, -3, -4, -5}
  assert( max == -1 and i == 1 and j == 1)

  max, i, j = gss.subsums {-2, 1, -3, 4, -1, 2, 1, -5, 4}
  assert( max == 6 and i == 4 and j == 7)
end)

run('Dynamic programming', function()
  local max, i, j = gss.dynamic {1, 2, 3, 4, 5}
  assert( max == 15 and i == 1 and j == 5)

  max, i, j = gss.dynamic {-1, -2, -3, -4, -5}
  assert( max == -1 and i == 1 and j == 1)

  max, i, j = gss.dynamic {-2, 1, -3, 4, -1, 2, 1, -5, 4}
  assert( max == 6 and i == 4 and j == 7)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))