1.最大连续子序列的和。
#include<stdio.h>
int this_num,max_num;
int a[100005];
int main()
{
//几种情况考虑的比较好了
int case_num,i,j,k;
scanf("%d",&case_num);
for(i=1;i<=case_num;i++)
{
this_num=0;
max_num=-19000;
int n,be=0,en=0;
scanf("%d",&n);
for(j=0;j<n;j++) scanf("%d",&a[j]);
k=1;
for(j=0;j<n;j++)//这地方有一个技巧!!!
{
this_num+=a[j];
if(this_num>max_num)
{
max_num=this_num;
be=k;
en=j+1;
}
if(this_num<0)//这地方自己有一一个疑问可得到自己解决。就是前面是一串正数后面又加上负数etc..
{
k=j+2;
this_num=0;
}
}
printf("Case %d:\n",i);
printf("%d %d %d\n",max_num,be,en);
if(i!=case_num) printf("\n");
}
return 0;
}//这个代码是适应一连串的负数的,不过一开始max_num要初始化为一个较小的负数。
2.最大上升(非上升)连续子序列
代码1:(正确版)
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
{
if(a[j]<=a[i]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
代码2: (错误版)
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
if(a[j]>=a[i]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
//现在看起来当初自己学的也不够扎实,毕竟还得自己亲自编一遍吧。代码1dp[i]是真的已经推出来了,是从前往后走的。。代码2就类似一个排序的程序shit。。。
3.LCS 最长公共子序列
这个自己随便写了一个就过了。 好像的确是建一个二维数组dp[N][N]; 算法复杂度O(nm);