一個最大上升子序列問題
dp[i] 記錄了在i之前且在i位置上的最大上升序列和，dp[i]等於前面a[j]<a[i]且dp[j]值的最大與a[i]的和
[cpp]
<span style="font-size:18px;color:#000099;"><strong>#include<stdio.h>
__int64 dp[1010],maxn,t;
int a[1010];
int main()
{
int n,i,j;
while(scanf("%d",&n)&&n)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
dp[0]=a[0];t=0;
for(i=1;i<n;i++)
{
maxn=0;
for(j=0;j<i;j++)
if(a[j]<a[i]&&dp[j]>maxn) maxn=dp[j];
dp[i]=a[i]+maxn;
t=t>dp[i]?t:dp[i];
}
printf("%I64d\n",t);
}
return 0;
}
</strong></span>
