字节跳动2018秋招编程题——空气质量

偶然在网上看到的编程题，感觉挺有意思的。但是没有在网上找到对应的题目和解析，所以没法测试算法的正确性，下面写一下思路，供大家参考，如果有纰漏之处还望指出。
关于不曾下降过的序列递增应该由如下方式组成：
【以a结尾的非严格递增序列】 * 1
【等于a的子序列】 * （t-2）
【不小于a的非严格递增序列】 * 1 可以用反证法证明上述情况成立。
具体解法如下：

#include <iostream>
#include <unordered_map>
#include <list>
#include <vector>
using namespace std;


int forwardFun(vector<int> &v, int num)  //大于等于num的递增子序列长度
{
    vector<int> res;
    for(int n : v)
    {
        if(n >= num)
        {
            if(res.empty())
                res.push_back(n);
            else
            {
                if(n >= res[res.size()-1])
                    res.push_back(n);
                else
                {
                    for(int i = 0; i < res.size() ; i++)
                        if(v[i] > n)
                        {
                            v[i] = n;
                            break;
                        }
                }
            }
        }
    }
    return res.size();
}


int backFun(vector<int> v, int num)  // 以num结尾的非严格递增序列
{
    reverse(v.begin(), v.end());
    vector<int> res;
    for(int i = 0 ; i < v.size(); i++)
    {
        if(v[i] == num)
        {
            if(res.empty())
                res.push_back(v[i]);
            else
            {
                if(res[res.size()-1] != num)
                    for(int i = 0 ; i < res.size() ; i++)
                    {
                        if(res[i] < num)
                        {
                            res[i] = num;
                            break;
                        }
                    }
                else
                {
                    res.push_back(v[i]);
                }
            }
        }
        else if(v[i] < num)
        {
            if(res.empty())
                continue;
            if(v[i] <= res[res.size()-1])
            {
                res.push_back(v[i]);
            }
            else
            for(int j = 0 ; j < res.size() ;j++)
            {
                if(res[i] < v[i])
                {
                    res[i] = num;
                    break;
                }
            }
        }
    }
    return res.size();
}

int main()
{
    int n,t;
    cin >> n >> t;
    vector<int> v(n),dp(n);
    for(int i = 0 ; i < n;i++)
        cin >> v[i];
    unordered_map<int, int> map,sameNum;

    for(int i = n-1 ; i >= 0 ; i--)
    {
        if(map.count(v[i]) == 1)
        {
            sameNum[v[i]] += 1;
            continue;
        }

        sameNum[v[i]] = 1;
        int num = backFun(v, v[i]);
        map[v[i]] = num;
    }
    int ans = 0;
    for(auto it = map.begin(); it != map.end(); it++)
    {
        int num = it->second, tmp_res = 0;
        int count = sameNum[it->first];
        tmp_res = num + count * (t-2);
        tmp_res += forwardFun(v, it->first);
        an***ax(ans, tmp_res);
    }
    cout << ans << endl;
    return 0;
}