Redraiment的走法
算法知识视频讲解
中等 通过率：25.60% 时间限制：1秒 空间限制：32M
知识点
排序
题目
题解(22)
讨论(186)
排行
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？

本题含有多组样例输入

输入描述：
输入多组数据，1组有2行，第1行先输入数组的个数，第2行再输入梅花桩的高度

输出描述：
一组输出一个结果

示例1
输入：
6
2 5 1 5 4 5
3
3 2 1
复制
输出：
3
1
复制
说明：
6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5
从第5格开始走最多有2步,4 5
所以这个结果是3。 

#include <iostream>
#include <vector>

using namespace std;

/*
* 思路：将数组的值进行冒泡比较，依次将较大的值存储vecOut数组
* 步骤：
* 第一步：输入数组个数n和值inputVec;
* 第二步：进行冒泡排序，第一个值大于后面所有值，则输出个数为1；
*     如果第一个值小于第二个值，则输出个数加1；第二个数小于第三个数，则继续加1
*/

void increaseVec(vector<int> inputVec)
{
    int inputVecLen = inputVec.size();
    //vector<int> outputVec(inputVecLen,1);
    vector<int> outputVec;
    int k = 1;
    for(int i = 0;i < inputVecLen; i++)
    {
        outputVec.push_back(1);
        for(int j = 0;j < i; j++)
        {
            if(inputVec[j] < inputVec[i])
            {
                outputVec[i] = max(outputVec[i], outputVec[j]+1);
                if(outputVec[i] > k) {
                    k = outputVec[i];
                }
            }
        }

    }

    cout<<k<<endl;
}
int main()
{
    int n;
    while(cin>>n) {
        vector<int> vec;
        for(int i = 0; i < n; i++) {
            int temp;
            cin>>temp;
            vec.push_back(temp);
        }
        increaseVec(vec);


    }
}