algorithm - How do we solve the given scenario efficiently? -

we given maze in need visit many rooms possible. specialty of maze once enter room lead rooms higher tag in direction move . b , c decide move in opposite directions trying luck maximize number of rooms search .(they can start room , need not same)

we need find out maximum number of rooms can searched.

1. access room higher tag allowed, not adjacent rooms or next room higher tag.  2. tags unique.  

so given input:

12 11 10 1 2 3 4 13 6 7 8 5 9  answer 12: (1,2,3,4,6,7,8,9) b , (5,10,11,12) c. 

i thought of solving using longest increasing sub sequence first right , left.and count of unique elements in above 2 sub sequence answer.

but logic seems fail,how can done?

my program below computes maximum number of rooms searched. has time complexity of o(n^3). modified dp algorithm computing longest increasing sequence available online solve op's problem. addresses op's concerns on arrays {1,4,6,2,5}. rightly max value 5 previous example. so, used idea @beyelerstudios need compute longest increasing subsequence both left right , right left. but, there caveat. if compute left right max sequence, sequence right left should on remaining elements. example:
array {1, 4, 6, 2, 5}. if forward rooms selected {1, 4, 5 }, reverse longest increasing sequence should computed on left out elements {6, 2}.

below program:

#include <iostream> using namespace std;   // compute max increasing sequence right left. int r2lrooms (int arr[], int n)  {      int dp[n];     int =0, j = 0;     int max = 0;      ( = 0; < n; i++ ) {         dp[i] = 1;     }      (i = n-2; >= 0; i--) {         ( j = n-1; j > i; j-- ) {             if ( arr[i] > arr[j] && dp[i] < dp[j] + 1) {                 dp[i] = dp[j] + 1;             }         }     }      ( = 0; < n; i++ ) {         if ( max < dp[i] ) {             max = dp[i];         }     }     return max;  }   // compute max rooms. int maxrooms( int arr[], int n ) {      int dp[n], revarray[n];     int =0, j = 0, k = 0;     int currentmax = 0;     int forwardmax = 0, reversemax = 0;      ( = 0; < n; i++ ) {         dp[i] = 1;     }      // first case except first elem, others in revarray     (i=1; < n; i++, k++) {         revarray[k] = arr[i];     }     reversemax = r2lrooms (revarray, k);     forwardmax = 1;     if (currentmax < (forwardmax + reversemax)) {         currentmax = forwardmax + reversemax;     }     cout << "forwardmax revmax , currentmax are: " << forwardmax << " " << reversemax << " " << currentmax << endl;     cout << endl;      ( = 1; < n; i++ ) {         k = 0;         forwardmax = 1;         reversemax = 0;          cout << "forward elems arr[" << << "]=" << arr[i] << endl;          ( j = 0; j < i; j++ ) {             if ( arr[i] > arr[j] && dp[i] < dp[j] + 1) {                 dp[i] = dp[j] + 1;                 forwardmax = dp[i];                  cout << arr[j] << " ";             }             else {                 // element not in dp calculation, put in revarray.                 revarray[k] = arr[j];                 k++;             }         }         // copy remaining elements in revarray.         ( j = i+1; j < n; j++ ) {             revarray[k] = arr[j];             k++;         }         cout << endl;         reversemax = r2lrooms (revarray, k);         if (currentmax < (forwardmax + reversemax)) {             currentmax = forwardmax + reversemax;         }         cout << "forwardmax revmax , currentmax are: " << forwardmax << " " <<  reversemax << " " << currentmax << endl;         cout << endl;     }     cout << " max rooms searched " << currentmax << endl;     return currentmax; }  int main (void) {      int arr[] = {12, 11, 10, 1, 2, 3, 4, 13, 6, 7, 8, 5, 9 };     int size = sizeof(arr) / sizeof(int);      cout << maxrooms (arr, size);   }