Question

一道ACM的题目，求用C语言递归编写的算法，非常感谢啊!!!：求上升子序列和的最大值

Description

由非负整数bi(0≤i<m)组成的序列，当b0<b1<...<bm-1时被称为长度为m的上升序列。
一个长度为n的序列a0, a1, ...,an-1，存在多种上升子序列：
ai0, a i1, ..., a ik (0≤i0< i1<...<ik<n)。
例如：序列1, 7, 3, 5, 9, 4, 8的上升子序列有1, 7、3, 5, 8、1, 3, 5, 9等。这些上升子序列中序列和最大为18，为上升子序列1, 3, 5, 9的和。
对于给定的序列，求出上升子序列和的最大值。</ik<n)。
</m)组成的序列，当b0<b1<...<bm-1时被称为长度为m的上升序列。

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
要详细代码！！！谢谢！！

Answer 1

您好！
这是杭电acm的第1087题，答案如下：
#include<stdio.h>
__int64 a[10009],sum[10009],Maxsum,max;
int main()
{
int i,j,n;
while(scanf("%d",&n),n!=0)
{
for(i=0;i<n;i++)
scanf("%I64d",&a[i]);
sum[0]=a[0];
for(i=1;i<n;i++)
{ Maxsum=0;
for(j=0;j<i;j++)
if(a[i]>a[j])
{
if(Maxsum<sum[j])
Maxsum=sum[j];
}

sum[i]=Maxsum+a[i];
}
max=sum[0];
for(i=1;i<n;i++)
if(max<sum[i])
max=sum[i];
printf("%I64d\n",max);

}
return 0;
}
希望对您有帮助！

Answer 2

百度hdu1087 跟这题一样的