# algorithm – 我们如何有效地解决给定的场景？

``````1. Access to any room with a higher tag is allowed, not just adjacent rooms or the next room with a higher tag.
2. Tags are unique.
``````

``````12 11 10 1 2 3 4 13 6 7 8 5 9
the answer is 12: (1,2,3,4,6,7,8,9) for B and (5,10,11,12) for C.
``````

``````#include <iostream>
using namespace std;

// compute the max increasing sequence from right to left.
int r2lRooms (int arr[], int n)
{

int dp[n];
int i =0, j = 0;
int max = 0;

for ( i = 0; i < n; i++ ) {
dp[i] = 1;
}

for (i = n-2; i >= 0; i--) {
for ( j = n-1; j > i; j-- ) {
if ( arr[i] > arr[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
}

for ( i = 0; i < 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 i =0, j = 0, k = 0;
int currentMax = 0;
int forwardMax = 0, reverseMax = 0;

for ( i = 0; i < n; i++ ) {
dp[i] = 1;
}

// First case is that except for first elem, all others are in revArray
for (i=1; i < n; i++, k++) {
revArray[k] = arr[i];
}
reverseMax = r2lRooms (revArray, k);
forwardMax = 1;
if (currentMax < (forwardMax + reverseMax)) {
currentMax = forwardMax + reverseMax;
}
cout << "forwardmax revmax and currentmax are: " << forwardMax << " " << reverseMax << " " << currentMax << endl;
cout << endl;

for ( i = 1; i < n; i++ ) {
k = 0;
forwardMax = 1;
reverseMax = 0;

cout << "Forward elems for arr[" << i << "]=" << arr[i] << endl;

for ( 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 was not in DP calculation, so put in revArray.
revArray[k] = arr[j];
k++;
}
}
// copy the remaining elements in revArray.
for ( 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 and 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);

}
``````