上升序列和的最大值
EOJ上2958，由非负整数bi(0≤i 一个长度为n的序列a0, a1, ...,an-1，存在多种上升子序列：
ai0, a i1, ..., a ik (0≤i0< i1<... 例如：序列1, 7, 3, 5, 9, 4, 8的上升子序列有1, 7、3, 5, 8、1, 3, 5, 9等。这些上升子序列中序列和最大为18，为上升子序列1, 3, 5, 9的和。
对于给定的序列，求出上升子序列和的最大值。
Input
第1行：整数T（1≤T≤10）为问题数
第2行：第1个问题的整数n（1≤n≤5000）
第3行：n个整数ai（0≤ai≤4000）,由一个空格隔开。这些数的值有些可能是相等的。
后面是第2 ∽ T个问题的数据。格式与第1个问题相同。
Output
对于每个问题，输出一行问题的编号（0开始编号，格式：case #0: 等），然后在一行中输出上升子序列和的最大值。
Sample Input
2
7
1 7 3 5 9 4 8
4
100 20 20 3
Sample Output
case #0:
18
case #1:
100
我不知道为什么wa了。。。。
#include<stdio.h>
#include<stdlib.h>
int compare(void const*a,void const*b)
{
return *(int*)b-*(int*)a;
}
void solve()
{
int n,sum;
long long int max=0;
int i,j,k,t=0;
int a[5005];
long long int b[5005];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
sum=a[i];
max=a[i];
for(j=i+1;j<n;j++)
{
if(a[j]>max)
{
sum+=a[j];
max=a[j];
}
for(k=j+1;k<n;k++)
{
if(a[k]>max)
{
sum+=a[k];
max=a[k];
}
}
b[t]=sum;
sum=a[i];
max=a[i];
t++;
}
}
qsort(b,t,sizeof(long long int),compare);
printf("%I64d\n",b[0]);
}
int main()
{
int i,t;
scanf("%d",&t);
for(i=0;i<t;i++)
{
printf("case #%d:\n",i);
solve();
}
return 0;
}
[解决办法]
请注意题中：
第2行：第1个问题的整数n（1≤n≤5000）
试输入：
1
1
1
LZ程序将输出错误结果。
[解决办法]
long long int b[5005];
qsort(b,t,sizeof(long long int),compare);
int compare(void const*a,void const*b){return *(int*)b-*(int*)a;}
。。。
[解决办法]
longest increasing sequence
