题意:
求解最大递增子序列。
例如:3 1 3 2
输入 3 个数 1 3 2
则递增子序列有 {1} {3} {2} {1 3} {1 2} ,故输出子序列的最大和 4
解题思路:
x[n](n个数) 数组存储 输入的数据
dp[i] 用来记录 前 i+1 {数据从下标为0开始存储}个数的 最大结果
遍历dp[] 找到最大值即可。
因 G20 网站暂停提交
明天测试代码。
2016.08.27 代码提交成功!
代码如下:
#include<bits/stdc++.h>
using namespace std;
int x[];
int dp[];
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
int i,j,maxx=;
for(i=; i<n; i++)
{
scanf("%d",&x[i]);
}
memset(dp,,sizeof(dp));
dp[]=x[];
for(i=; i<n; i++)
{
for(j=; j<i; j++)
{
if(x[i]>x[j])
dp[i]=max(dp[j],dp[j]+x[i]);
}
dp[i]=max(dp[i],x[i]);
maxx=max(dp[i],maxx);
}
printf("%d\n",maxx);
}
return ;
}