题目的主要信息：

从n个数中选择任意一个起点，从前到后，但只能从数值较小往数值较大走，问最多能走多少步。

这实质上是求最长上升子序列。

方法一：

采用动态规划。动态数组为dp，首先初始化为1。dp[i]的含义是以第i个位置结尾最多能走的步数，即以nums[i]结尾的最长上升子序列的长度。动态规划过程如下：

1. 初始化dp[0]=1
2. 从i=1开始，遍历一遍0-i元素，如果nums[j]<nums[i]，dp[i]取dp[i]和dp[j]+1中的最大值更新。
3. 每次遍历完0-i元素后，如果dp[i]大于目前已知的最大步数，则更新最大步数result。 具体做法：

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

int main(){
    int n;
    while(cin>>n){
        int temp;
        vector<int> nums;
        for(int i=0;i<n;++i){//存储n个数
            cin>>temp;
            nums.push_back(temp);
        }
        vector<int> dp(nums.size(),1);//dp[i]的含义是以第i个桩子结尾走的最多的步数
        int result=0;
        for(int i=1;i<nums.size();++i){//从第1个位置开始计算
            for(int j=0;j<i;++j){//遍历i位置之前的所有元素
                if(nums[i]>nums[j]){//如果有元素值更小
                    dp[i]=max(dp[i],dp[j]+1);//更新dp[i]的值
                }
            }
            if(dp[i]>result){//找到最多的步数
                result=dp[i];
            }
        }
        cout<<result<<endl;
    }
    return 0;	
}

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，双重循环。
• 空间复杂度：$O(n)O(n)$，动态数组大小为n。

方法二：

具体做法：

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

int BinarySearch(int v, vector<int>& dp, int len){  //二分查找函数
    int left = 1, right = len, mid;
    while(left <= right){
        mid = (right + left) / 2;
        if(dp[mid] >= v){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

int main(){
    int n;
    while(cin>>n){
        int temp;
        vector<int> nums;
        for(int i=0;i<n;++i){//存储n个数
            cin>>temp;
            nums.push_back(temp);
        }
        vector<int> dp(n+1,0);//dp[i]的含义是长度为i的序列最小结尾的数字
        int len=1;//len的含义是当前最大的步数
        dp[len]=nums[0];
        for(int i=1;i<nums.size();++i){//从第1个位置开始计算
            if(nums[i]>dp[len]){//说明可以有更长的序列
                len++;
                dp[len]=nums[i];
            }else{
                int pos=BinarySearch(nums[i], dp, len);//找到第一个比nums[i]小的元素
                dp[pos]=nums[i];//替换为nums[i]
            }
        }
        cout<<len<<endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，数组nums的长度为 n，我们依次用数组中的元素去更新dp数组，而更新dp数组时需要进行二分查找。
• 空间复杂度：$O(n)O(n)$需要额外使用长度为n的dp数组。