int lis(std::vector<int> nums)
{
    int n = nums.size();
    int max = 0, i, j;
    std::vector<int> buf(n, 1);
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (nums[i] > nums[j] && buf[i] < buf[j] + 1)
                buf[i] = buf[j] + 1;

    for (i = 0; i < n; i++)
        if (max < buf[i])
            max = buf[i];

    return max;
}






int ways(int m, int n)
{
    if (m == 0 || n == 0)
        return 0;
    int** f = new int* [m];
    for (int i = 0; i < m; i++)
    {
        f[i] = new int[n];
        f[i][0] = 1;
    }
    for (int j = 0; j < n; j++)
        f[0][j] = 1;
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            f[i][j] = f[i - 1][j] + f[i][j - 1];
    int res = f[m - 1][n - 1];

    for (int i = 0; i < m; i++)
        delete[] f[i];
    delete[] f;
    return res;
}