Towers

You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower or begin a new tower. What is the minimum possible number of towers?

Example:

Input: n = 5, arr = {3, 8, 2, 1, 5}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int towers(int n, vector<int> &arr)
{

    vector<int> dp;
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];

        auto it = upper_bound(dp.begin(),
                              dp.end(), x);
        if (it == dp.end())
            dp.push_back(x);
        else
            *it = x;
    }
    return dp.size();
}

int main()
{
    int n = 5;

    vector<int> arr = {3, 8, 2, 1, 5};
    cout << towers(n, arr) << "\n";

    return 0;
}