我们老师自己出了一道加强版，数据 $10^7$ 。

我这个 O(n) TLE 了一个点，求怎么加快。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
int n;
int a[N];
int dp[10];
int len[10]; 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
//		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=a[i];j++)
		{
			if(len[j]>len[a[i]])
			{
				len[a[i]]=len[j];
				dp[a[i]]=dp[j];
			}
			if(len[a[i]]==len[j])
			{
				dp[a[i]]=max(dp[a[i]],dp[j]);
			}
		}
		len[a[i]]++;
		dp[a[i]]+=a[i];
		printf("%d ",dp[a[i]]);
	}
	return 0;
}