Last one picked

Problem Statement:

Finally, after years of anticipation, the first basketball court has been opened on Mars, so the governor has decided to hold a basketball exercise session. 2⋅n students have come to the governor’s exercise session, and he lined up them into two rows of the same size (there are exactly N people in each row). Students are numbered from 1 to N in each row in order from left to right.

1 2 3 4 5 ... n
1 2 3 4 5 ... n

Now the governor wants to choose a team to play basketball. He will choose players from left to right, and the index of each chosen player (excluding the first one taken) will be strictly greater than the index of the previously chosen player. To avoid giving preference to one of the rows, the governor chooses students in such a way that no consecutive chosen students belong to the same row. The first student can be chosen among all 2N students (there are no additional constraints), and a team can consist of any number of students.

The governor thinks, that in order to compose a perfect team, he should choose students in such a way, that the total height of all chosen students is maximum possible. Help the governor to find the maximum possible total height of players in a team he can choose.

Constraints:

• 0 ≤ A_i, B_i ≤ 10⁹ (1 ≤ i ≤ N)

Subtask 1: (20 points)

• 1 ≤ N ≤ 15

Subtask 2: (80 points)

• 1 ≤ N ≤ 10⁵

Input Format:

• The first line contains a single integer N
• The next line contain N integers representing the heights in A
• The next line contain N integers representing the heights in B

Output Format:

• Print a single line for each testcase containing the maximum sum of heights

Sample input:

5
9 3 5 7 3
5 8 1 4 5

Sample output:

29

Solution:

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp1 = [0] * n
dp2 = [0] * n

dp1[0] = a[0]
dp2[0] = b[0]

for i in range(1, n):
	dp1[i] = max(dp1[i - 1], dp2[i - 1] + a[i])
	dp2[i] = max(dp2[i - 1], dp1[i - 1] + b[i])

print(max(dp1[n - 1], dp2[n - 1]))