To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements

Question

This problem is from codechef.Can anyone please help me out with this one as I am unable to find out the subproblem.Thanks in advance!

Problem -: In IPL 2025, the amount that each player is paid varies from match to match. The match fee depends on the quality of opposition, the venue etc.

The match fees for each match in the new season have been announced in advance. Each team has to enforce a mandatory rotation policy so that no player ever plays three matches in a row during the season.

Nikhil is the captain and chooses the team for each match. He wants to allocate a playing schedule for himself to maximize his earnings through match fees during the season.

Input format

Line 1: A single integer N, the number of games in the IPL season.

Line 2: N non-negative integers, where the integer in position i represents the fee for match i.

Output format

The output consists of a single non-negative integer, the maximum amount of money that Nikhil can earn during this IPL season.

Sample Input 1

5

10 3 5 7 3

Sample Output 1

23

(Explanation: 10+3+7+3)

Sample Input 2

8

3 2 3 2 3 5 1 3

Sample Output 2

17

(Explanation: 3+3+3+5+3)

Answer 1

Let $X_k$ be the largest sum up to the k-th element that follows the rules and doesn't include the k-th element itself. Let $Y_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, but not the one before. Let $Z_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, and the one before as well. Let $a_k$ be the array elements.

Then $X_{k+1} = max (X_k, Y_k, Z_k)$, $Y_{k+1} = X_k + a_{k+1}$, and $Z_{k+1} = Y_k + a_{k+1}$. Start with $X_0 = Y_0 = Z_0 = 0$, calculate $X_n, Y_n, Z_n$ and the solution is $max (X_n, Y_n, Z_n)$.