To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:47:50Z https://cs.stackexchange.com/feeds/question/67071 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/67071 -1 To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements Sushovan Haldar https://cs.stackexchange.com/users/61463 2016-12-07T18:31:07Z 2016-12-08T11:05:15Z <p>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!</p> <p>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.</p> <p>The match fees for each match in the new season have been announced in advance. <strong>Each team has to enforce a mandatory rotation policy so that no player ever plays three matches in a row during the season.</strong></p> <p>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.</p> <p><strong>Input format</strong></p> <p>Line 1: A single integer N, the number of games in the IPL season.</p> <p>Line 2: N non-negative integers, where the integer in position i represents the fee for match i.</p> <p><strong>Output format</strong></p> <p>The output consists of a single non-negative integer, the maximum amount of money that Nikhil can earn during this IPL season.</p> <p>Sample Input 1</p> <p>5 </p> <p>10 3 5 7 3 </p> <p>Sample Output 1</p> <p>23</p> <p>(Explanation: 10+3+7+3)</p> <p>Sample Input 2</p> <p>8</p> <p>3 2 3 2 3 5 1 3</p> <p>Sample Output 2</p> <p>17</p> <p>(Explanation: 3+3+3+5+3)</p> https://cs.stackexchange.com/questions/67071/-/67097#67097 0 Answer by gnasher729 for To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements gnasher729 https://cs.stackexchange.com/users/17408 2016-12-08T11:05:15Z 2016-12-08T11:05:15Z <p>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. </p> <p>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)\$. </p>