What approach should I use in this question? approach I used below is not getting accepted

Question

IPL Auctions are back. There are n players who will go under hammer in the sequence. There prices are given in a form an array in the order. A team wants to buy as much as player they can, but they have a condition that, they can only buy the current player if and only if the price of their last buyed player is less than the price of current player. Team can buy any player as their first player.

You need to find out the maximum player the team can buy following the above condition.

Input Format

First line of input contains an integer N, denoting the number of players in the auction.

Second line of input contains N space seperated integers denoting prices of players.

Constraints

1 ≤ N ≤ 10^5

0 ≤ A[i] ≤ 10^6

Output Format

The largest number of players they can buy

Sample Input : array size = 6

5 8 3 7 9 1

Sample Output : 3

Explanation:

Largest number of the player will be when team will buy players with prices 5,8 and 9 that is 3.

What I have tried:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int n ; 
    cin>>n;
    int a[n];
    for(int i = 0;i<n;i++){
        cin>>a[i];
    }
    int mxcount = 0;
    for(int i = 0;i<n;i++){
        int  k = i;
         int count = 1;
        for(int  j = i;j<n;j++){
            
            if(a[j] > a[k]){
                count++;
                k++;
            }
        }
        mxcount = max(mxcount,count);
    }
    cout<<mxcount;
    return 0;
}

Answer 1

Inner for loop logic that have been used is wrong because the k-th index should always be the last player you have bought in the Auction, instead you are incrementing k-value instead of using the last bought player index.

We can implement below algorithm for this problem: "We will always have two options during auction either to buy or not. so we can simply use a recursive approach of choosing and not choosing a player "

def auctionOptimizer(players, index_of_last_player_picked, current_index_of_player):
  if(current_index_of_player >= players.size()) :
    return 0;
  if (players[current_index_of_player] > players[index_of_last_player_picked]):
      int count_if_current_player_picked = 1 + auctionOptimizer(players, current_index_of_player, current_index_of_player+1);
      int count_if_current_player_not_picked = auctionOptimizer(players, index_of_last_player_picked, current_index_of_player+1);
      return max(count_if_current_player_picked, count_if_current_player_not_picked)
  return auctionOptimizer(players, index_of_last_player_picked, current_index_of_player+1);

def main():
    //Take players input array here
    int max_players_we_can_buy = 0;
    for(int player_index = 0 ; player_index < players.size(); players_index++) {
        int count_if_current_player_index_picked = 1 + auctionOptimizer(players, player_index, player_index+1);
        max_players_we_can_buy = max(max_players_we_can_buy, count_if_current_player_index_picked);
    }
    return max_players_we_can_buy;
    

We can further optimize this problem as there will be overlapping sub-problems i.e., we will be calling same function calls multiple times which would result in timeout. We can using DP for further optimising above approach.

Please approve the solution, if you found this helpful,

Thanks :-)