water pool amount

gistfile1.lua

-- 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)