Skip to content

Instantly share code, notes, and snippets.

@jianchenglee jianchenglee/gist:7262518
Last active Dec 27, 2015

Embed
What would you like to do?
water pool amount
-- author ljc
-- 1) find the max value, split the array to 2 array
-- 2) compute the increment ,get 2 increment array
-- 3) get the result by the increment value(if there are a minus value,then retain water,until one by one accumulation value become plus,then go on next)
waterpool={2,4,3,5,1,2,3,2,3,7,7,6,7,6,4,5}
testcase_1 = {2,5,1,2,3,4,7,7,6}
testcase_2 = {2,5,1,3,1,2,1,7,7,6}
testcase_3 = {6,1,4,6,7,5,1,6,4}
function watertotal(o)
-- v1:tempvalue total: result value
-- v_max,i_max: the biggest value and the index of the input array
-- waterpool_q1: first half increment value array waterpool_q2: secopd half increment value array
local v1,v_max,i_max,total=0,0,0,0,0;
local waterpool_q1={};
local waterpool_q2={};
local allnumber=table.maxn(o)
--1)
for i,v in ipairs(o) do
if v>v_max then
v_max=v
i_max=i
end
end
--2)
-- generate waterpool_q1
for i=1,i_max-1,1 do
--print(o[i]-v1)
table.insert(waterpool_q1,o[i]-v1)
v1=o[i]
end
-- generate waterpool_q2
v1=0
for i=allnumber,i_max,-1 do
--print(o[i]-v1)
table.insert(waterpool_q2,o[i]-v1)
v1=o[i]
end
--3)
-- the result of waterpool_q1
v1=0
for i,v in ipairs(waterpool_q1) do
if v<0 and v1>=0 then
v1=v
total=total+math.abs(v1)
elseif (v1+v<0) then
v1=v1+v
total=total+math.abs(v1)
elseif v+v1>=0 then
v1=0
end
--print(math.abs(v1))
end
-- the result of waterpool_q1
v1=0
for i,v in ipairs(waterpool_q2) do
if v<0 and v1>=0 then
v1=v
total=total+math.abs(v1)
elseif (v1+v<0) then
v1=v1+v
total=total+math.abs(v1)
elseif v+v1>=0 then
v1=0
end
--print(math.abs(v1))
end
print(total)
end
-- test the function
watertotal(waterpool)
watertotal(testcase_1)
watertotal(testcase_2)
watertotal(testcase_3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.