View Code of Problem 1037

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

#define maxN 5010
int dp[maxN],key[maxN],num[maxN];
int max(int x,int y){return x>y?x:y;}

int main()
{
	int a,b,k,i,j,n;
	while(~scanf("%d",&n))
	{
	    for(i=0;i<n;i++)
	    {
	        scanf("%d",&key[i]);
	        dp[i]=num[i]=1;
	        for(j=i-1;j>=0;j--)
	        {
	            if(key[j]>key[i])
	            {
	                if(dp[j]+1>dp[i])
	                {
	                    dp[i]=dp[j]+1;
	                    num[i]=num[j];
	                }
	                else if(dp[i]==dp[j]+1)
	                num[i]+=num[j];
	            }
	        }
	        for(j=i-1;j>=0;j--)
	        {
	            if(key[i]==key[j])
	            num[j]=0;
	        }
	    }
	    int max_n=0;
	    int tnum=0;
	    for(i=0;i<n;i++)
	    if(dp[i]>max_n)
	    max_n=dp[i];
	    for(i=0;i<n;i++)
	    if(dp[i]==max_n)
	    tnum+=num[i];
	    printf("%d %d\n",max_n,tnum);
	}
}