choosing-the-judges-7

Harry was contesting to be the most stylist person in his college. He had to collect maximum points from the judges to be able to win. However there was a problem. The judges were sitting in a line and each pair of adjacent judges had ego issues with each other. So if one judge gave X points to Harry then the next judge won’t give him any points. Harry had a friend in the organizing team and through him he had found out the exact points he would get from each judge if he chose their score to be considered. Help him find out the maximum points he can score.

INPUT
The first line of input contains the number of test cases, T.
0 < T < = 10
Each test case starts with a number N, the number of judges.
0 ≤ N < = 10^4. 
The next line will have N numbers, number of points each judge gave Harry
0 < = X(i) < = 10^9.
 The order of the judges does not change.

OUTPUT
For each test case print “Case T: A” without quotes in a single line. 
T is the case number, starting with 1.
A is the maximum number of points Harry can collect.

SAMPLE INPUT
2
5
1 2 3 4 5
1
10

SAMPLE OUTPUT
Case 1: 9
Case 2: 10

Explanation

Case 1 : 
Harry chooses judges 1,3 and 5 with points 1 ,3 and 5 respectively to add up to 9 points in total.
Case 2:
There is only one judge so Harry chooses his points alone.

Source: hackerearth | Difficulty: EASY


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc=input("")
tc=(int)(tc)
for k in range(tc):
	judges=input("")
	judges=(int)(judges)
	scores=input("").split(" ")
	dp=[]
	for i in range(judges):
		if i > 1:
			val1 = (int)(scores[i])
			val2= max(dp[j] for j in  range(i-2,-1,-1))
			dp.append(max(val1,val1 + val2))
		else:
			dp.append((int)(scores[i]))
	print("Case {}: {}".format(k+1,max(dp)))



t=eval(input())
for c in range(1,t+1):
	n=eval(input())
	a=list(map(int,input().split()))
	dp=[0]*n
	dp[0]=a[0]
	for i in range (n):
		if i-2>=0:
			dp[i]=max(dp[i-1],a[i]+dp[i-2])
		else:
			dp[i]=max(dp[i-1],a[i])
	print('Case',str(c)+':',str(dp[i])) 


import sys
sys.setrecursionlimit(10000)

def solve(i,arr,dp,n):
	if dp[i] != -1:
		return dp[i]
	if i>n-1:
		return 0
	if i==n-1:
		return arr[n-1]
	dp[i] = max(solve(i+1,arr,dp,n),arr[i]+solve(i+2,arr,dp,n))
	return dp[i]

tc = int(input())
ans = [0 for j in range(tc)]
for k in range(tc):
	n = int(input())
	dp = [-1 for i in range(n+1)]
	arr = list(map(int,input().split()))
	ans[k] = solve(0,arr,dp,n)
	dp =[]
for i in range(tc):
	print("Case %d: %d" %(i+1,ans[i]))
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
max_scores=[]
def max_score(points):
	max_scores.append(points[0])
	for index in range(1,len(points)):
		if index==1:
			max_scores.append(max(points[1],max_scores[0]))
		else:
			max_scores.append(max(max_scores[-1],max_scores[-2]+points[index]))
	return max_scores[-1]
	
cases=int(input())
for case in range(cases):
	judges=int(input())
	points=input()
	points=[int(i) for i in points.split(" ")]
	max_scores=[]
	print("Case "+str(case+1)+": "+str(max_score(points)))


import sys
dp=[]

def findsum(l):
	for i in range(2,len(l)):
		dp.append(max(dp[i-2] + l[i],dp[i-1]))
		#print dp
	return dp[len(dp)-1]
if __name__ == "__main__":
	t=int(input())
	x=1
	while x<=t:
		n1= sys.stdin.readline().rstrip('\n')
		n = int(n1)
		#print type(n)
		
		l=[int(i) for i in input().split(" ")]
		#print n
		#print l
		if n==1:        
			print("Case %d: %d" %(x,l[0]))
			x+=1
			continue
		if n>=2:
			dp.append(l[0])
			dp.append(max(l[0],l[1]))
			#print dp[1]
			print("Case %d: %d" %(x,findsum(l)))
		x+=1
		dp=[]


from heapq import *


def max_score(scores, n):
	"""
	:param scores: scores given by individual judge
	:param n: the number of judges
	:return: the maximum score johny boy can achieve
	"""
	if len(scores) != n:
		raise ValueError()

	if n <= 0:
		return 0
	if n == 1:
		return scores[0]

	opt = [0] * n
	heap = []
	last = scores[1]

	opt[0], opt[1] = scores[0], scores[1]
	heappush(heap, -opt[0])

	for i in range(2, n):
		opt[i] = scores[i] + -heap[0]
		heappush(heap, -last)
		last = opt[i]

	return max(opt)


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		print(("Case {}: {}".format(i + 1, max_score(a, n))))


if __name__ == '__main__':
	main()


import sys
sys.setrecursionlimit(10000)

def solve(i,arr,dp,n):
	if dp[i] != -1:
		return dp[i]
	if i>n-1:
		return 0
	if i==n-1:
		return arr[n-1]
	dp[i] = max(solve(i+1,arr,dp,n),arr[i]+solve(i+2,arr,dp,n))
	return dp[i]

tc = int(input())
ans = [0 for j in range(tc)]
for k in range(tc):
	n = int(input())
	dp = [-1 for i in range(n+1)]
	arr = list(map(int,input().split()))
	ans[k] = solve(0,arr,dp,n)
	dp =[]
for i in range(tc):
	print("Case %d: %d" %(i+1,ans[i]))
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc=input("")
tc=(int)(tc)
for k in range(tc):
	judges=input("")
	judges=(int)(judges)
	scores=input("").split(" ")
	dp=[]
	for i in range(judges):
		if i > 1:
			val1 = (int)(scores[i])
			val2= max(dp[j] for j in  range(i-2,-1,-1))
			dp.append(max(val1,val1 + val2))
		else:
			dp.append((int)(scores[i]))
	print("Case {}: {}".format(k+1,max(dp)))



t=eval(input())
for j in range(t):
	n=eval(input())
	a=[int(x) for x in input().split()]
	if n==0:
		print('Case %s: %s'%((j+1),0))
	elif n==1:
		print('Case %s: %s'%((j+1),a[0]))
	elif n==2:
		print('Case %s: %s'%((j+1),max(a[0],a[1])))
	else:
		u=[0]*(n)
		u[0]=a[0]
		u[1]=max(a[0],a[1])
		for i in range(2,n):
			u[i]=max(u[i-2]+a[i],u[i-1])
		print('Case %s: %s'%((j+1),u[n-1]))