此动态规划的状态转移方程为dp[i]=max{1, dp[j]+1 | j<i && A[j]>A[i]}.
#include<iostream> using namespace std; int height[26]; int dp[26]; int main(){ int k; while(cin>>k){ for(int i=0;i<k;i++){ cin>>height[i]; } int answer=0; for(int i=0;i<k;i++){ dp[i]=1; //初始化为1 for(int j=0;j<i;j++){ if(height[j]>=height[i]){ dp[i]=max(dp[j]+1,dp[i]); } } answer=max(answer,dp[i]); } cout<<answer<<endl; } return 0; }