华为机试-Redraiment的走法（较难）

题目描述

Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？

参考leetcode最长递增子序列
动态规划：dp数组保存每部最优解

 dp[i]=max(dp[i],dp[j]+1) 且j属于[0,i)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int ans=1;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j]<nums[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                    if(dp[i]>ans) ans=dp[i];
                }
            }

        }
        return ans;
    }
};

所以加上输入输出后：

#include<iostream>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int num;
    while(cin>>num){
        int input[num];
        for(int i=0;i<num;i++)
            cin>>input[i];
        int dp[num];int ans=1;
        for(int i=0;i<num;i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(input[j]<input[i])  
                {
                    dp[i]=max(dp[j]+1,dp[i]);
                    if(dp[i]>ans) ans=dp[i];
                }
            }
        }
        cout<<ans<<endl;
    }
}