子序列相关有关问题
子序列相关问题
1.最长连续递增（减）子序列的长度
样例输入：
7
1 7 4 6 9 2 10
样例输出：
3
#include<iostream>
#include<cstdio>
using namespace std;
int dp[10010],a[10101];
int main()
{
//freopen("input.txt","r",stdin);
int i,j;
int m,n;
int maxn;
while(cin>>m)
{
maxn=0;
for(i=1;i<=m;i++)
{
cin>>a[i];
dp[i]=1;
}
for(i=1;i<=m;i++)
{
if(a[i]>a[i-1])
dp[i]=dp[i-1]+1;
maxn=max(maxn,dp[i]);
}
cout<<maxn<<endl;
}
return 0;
}
2.最长不连续递增（减）子序列的长度
样例输入：
7
1 7 4 6 9 2 10
样例输出：
5
#include<stdio.h>
int main ()
{
int n,i,j;
int a[1006],dp[1006];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
dp[i]=1; // 初始化
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i]>a[j] && dp[i]<dp[j]+1) // a[j]和a[i]能构成一个上升子序列,然后把当前上升子序列的长度存到dp[i]中
dp[i]=dp[j]+1;
}
}
int t=0;
for(i=0;i<n;i++)
{
if(dp[i]>t)
t=dp[i];
}
printf("%d\n",t);
return 0;
}
3.最长不连续递增（减）子序列的和
样例输入：
7
1 7 4 6 9 2 10
样例输出：
30
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int a[1005],dp[1005]; // dp[]数组 表示子序列和
int main()
{
int n;
int i,j;
while((cin>>n)&&n)
{
for(i=0;i<n;i++)
{
cin>>a[i];
dp[i]=a[i]; // 初始化
}
for(i=0;i<n;i++)
for(j=0;j<i;j++)
{
if(a[i]>a[j] && dp[i]<dp[j]+a[i])
// a[j]和a[i]能构成一个上升子序列,然后把当前上升子序列的和存到dp[i]中
dp[i]=dp[j]+a[i];
}
int max=dp[0];
for(i=1;i<n;i++)
if(dp[i]>max)
max=dp[i]; // 求出最大值
cout<<max<<endl;
}
return 0;
}
4.最长公共子序列
for(i=1;i<=n;i++) // 求最长公共子序列
{
for(j=1;j<=n;j++)
{
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
5.不连续递增（减）子序列的个数
样例输入：
7
1 4 9 2 10
样例输出：
2
#include<stdio.h>
int main ()
{
int n,a[1000],b[1000],i,j,t;
while (~scanf("%d",&n))
{
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[i]=0; // 标记
}
int num=0;
for(i=0;i<n;i++)
{
if(b[i]==0)
{
b[i]=1; // 访问过
t=a[i];
for(j=i+1;j<n;j++)
{
if((b[j]==0)&&(t<=a[j]))
{
t=a[j];
b[j]=1;
}
}
num++;
}
}
printf("%d\n",num);
}
return 0;
}
6.最大连续子序列
样例输入：
6
3 -4 2 3 -1 8
样例输出：
12
#include<stdio.h>
int main()
{
int i,n,sum,max,flag,start,end,temp; //start、end记录最大连续子序列的开始位置和结束位置
int a[10001];
while(scanf("%d",&n) && n!=0)
{
flag=0; //判断当输入全为负数时，令flag=0，否则flag=1
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]>=0)
flag=1;
}
if(flag==0) //当全为负数时输出max=0
{
printf("0 %d %d\n",a[0],a[n-1]);
continue;
}
else
{
max=sum=a[0];
temp=start=end=0;
for(i=1;i<n;i++)
{
if(sum<0) // 一旦sum<0，令sum归零.
{
temp=i; // 记下 使sum<0 是第几项.(i)
sum=0;
}
sum+=a[i];
if(sum>max) // sum增加，变换start及end的值
{
max=sum;
start=temp;
end=i;
}
}
printf("%d %d %d\n",max,a[start],a[end]);
}
}
return 0;
#include<iostream>
#include<cstdio>
using namespace std;
int dp[101],a[101];
int main(int i,int j)
{
int m,n;
int maxn;
while(cin>>m)
{
maxn=-999;
for(i=0;i<m;i++)
{
cin>>a[i];
dp[i]=a[i];
}
for(i=0;i<m;i++)
{
for(j=0;j<i;j++)
//if(a[i]>a[i-1])
dp[i]=max(dp[j]+a[i],a[i]);
maxn=max(maxn,dp[i]);
}
cout<<maxn<<endl;
}
return 0;
}
7.最大递增（减）连续子序列
样例输入：
9
1 5 2 4 6 91 10 12
样例输出：
23
#include<iostream>
#include<cstdio>
using namespace std;
int dp[101],a[101];
int main(int i,int j)
{
int m,n;
int maxn;
while(cin>>m)
{
maxn=-999;
for(i=0;i<m;i++)
{
cin>>a[i];
dp[i]=a[i];
}
for(i=1;i<m;i++)
{
if(a[i]>a[i-1])
dp[i]=max(dp[i-1]+a[i],a[i]);
maxn=max(maxn,dp[i]);
}
cout<<maxn<<endl;
}
return 0;
}