47 星南二楼

2023-12-20 22:45:07

动态规划,相当于求解最长子序列问题

#include <iostream>  

using namespace::std;
using std::cout;
using std::cin; 

int n;
int a[5100],dp[5100];

int xnel(int n, int a[]) 
{
    int result = 0;
    for(int i=0; i<n; i++)
	{
        for(int j=0; j<i; j++)
		{
            if(a[j]<a[i])
			{
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        result = max(result,dp[i]+1);
    }
    return result;
}
  
int main() 
{  
    cin >> n;
    for(int i=0; i<n; i++)
    {
    	cin >> a[i];
	}
	std::cout << xnel(n, a);
    return 0;  
}

文章来源:https://blog.csdn.net/qq_64654845/article/details/135118603
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。