#algo #ruby

bunny.rb

# Gosho is a bunny. He lives in a forest full of hills. 
# Every hill has a different height and has a different amount of grass on it.
# He likes jumping very much, but he only jumps in zig-zag manner.
# I.e., he only jumps on a lower hill, then on an upper hill, then on a lower one again, 
# or he jumps on an upper hill, then on a lower one, then on an upper one again, and so on.
# Gosho likes eating. He likes eating even more than he likes jumping.
# You like Gosho and you want to help him.

# On the first line of input you get the number N - the number of hills in the vicinity of Gosho.
# On the next N lines, you get the pair P,Q, 
# where P is the height of the hill, and Q is the amount of grass it has.
# The question that Gosho wants answered is, what's the maximum amount of grass that he can eat
# while jumping zig-zag on the hills in his vicinity.
# Gosho eats all of the grass on every hill he jumps on.
# Gosho can only jump from left to right.


# Input:
# 7
# 3 1
# 2 3
# 5 4
# 3 2
# 1 7
# 3 1
# 3 4
# Expected output: 19

# Input:
# 3
# 5 4
# 3 2
# 1 7
# Expected output: 11

# Input:
# 4
# 3 1
# 2 3
# 5 4
# 3 2
# Expected output: 10

# Input:
# 5
# 3 1
# 4 100
# 2 3
# 5 4
# 3 2
# Expected output: 110

# Input:
# 5
# 5 5
# 3 8
# 6 3
# 2 1
# 4 9
# Expected output: 26

def solution hills, cur_hill, direction={}
	return 0 if hills.empty?

	s = []
	hills.each_with_index do |hill, index|
		if (direction[:direction] == :up && cur_hill[0] < hill[0]) ||
			(direction[:direction] == :down && cur_hill[0] > hill[0])

			h = hills.dup
			if direction[:direction] == :up
				s << solution(h[index..-1], hill, direction: :down)
			elsif direction[:direction] == :down
				s << solution(h[index..-1], hill, direction: :up)
			end
		end
	end

	s.empty? ? cur_hill[1] : cur_hill[1] + s.max
end

def get_hills
	hills = []
	num_hills = gets.chomp.to_i
	num_hills.times do
		hills << gets.chomp.split.map { |i| i.to_i }
	end
	hills
end

hills = get_hills

best = 0

hills.each_with_index do |hill, i|
	h = hills.dup[i..-1]
	
	res1 = solution(h, hill, direction: :down)
	best = [best,res1].max

	res2 = solution(h, hill, direction: :up)
	best = [best,res2].max
end

p best