Fight Club Restored

Let,

$t_i$ $=$ Number of battles on $i$th day $=$ ${n - i}$

$w_i$ $=$ Number of wins of $i$th fighter on $i$th day

$l_i$ $=$ Number of defeated battle of $i$th fighter on $i$th day ${= t_i - w_i = n - i - w_i}$

So, amount of money, a bettor can win by betting on $i$th day ${= w_i - l_i = w_i - (n - i - w_i) = 2 \times w_i - n + i}$

Here, we can calculate $w_i$ by counting the number of inversions of $i$th element of the given array which can be found by Binary Indexed Tree or Segment Tree while iterating from the $n$th element to the $1$st element of the array. We can use the coordinate compression technique to compress the array values so that the array values become smaller.

Now, the maximum amount of money can be found by using dynamic programming.

We have to run a $2D$ $dp$ of size $n \times k$ where $dp[i][j]$ is the maximum amount of money after $i$ days and total $j$ bets are done previously.

As, a bettor has to bet on exactly $2$ days in a row, on each day there are exactly $2$ options$:$ do not bet and go to the next day or bet on $i$th and $(i+1)$th day and go to $(i+3)$th day as go to $(i+2)$th day is forbidden if a bettor bets on $i$th day. So, the transition of $dp$ states will be as below.

${dp[i][j] = max(dp[i+1][j], dp[i+3][j+2] + money[i] + money[i+1])}$

Complexity: $\mathcal{O}(nlogn + n\times k)$

[Note: The $i$th element and the $j$th element forms an inversion if $a_i > a_j$ and $i<j$. The number of inversions of the $i$th element is the count of all $j$ for which the $i$th element and the $j$th element forms an inversion.]