本文总结一些常见的子列问题
问题模型: 给定一连串的数(或子串),问一些关于子列(和,差,公共子串,公共子序列等)的一些问题. (数字的个数在1e5之内,每个数的范围-1000~1000)和一些常见的思想与处理.
1 : 给定一串数字，求最大连续子序和.
#include<cstdio>
const int inf=1e9;
int main(){ //在线处理法,即输入一个数就判断一个数.
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int ans=0;
int res=-inf; //找最大,先令res为最小.
for(int i=1;i<=n;i++){
int m;
scanf("%d",&m);
ans += m;
if(ans > res){
res = ans ; //如果找到更大的值则更新res.
}
if(ans < 0) //加到这里时,ans已经为负,也不可能使后面的和变大,故重置ans的值.
ans = 0;
}
printf("%d\n",res);
}
}
这类题的变形题 (只需加一点小小的处理即可!)
2 : 给定一串数字，求最大子项和 且要为奇数 （或偶数,单纯的求最大子项和这个是人都会做.）.
思路 ：首先考虑极端情况,全是正数,则就全部加起来,如果和为奇数的输出,否则就输出和减去序列中的最小正奇数. 其次,考虑都是负数的情况,则答案就是最大负奇数. 最后,考虑一般情况,序列中既有正又有负,所以根据前面的讨论,我们需要找到该序列中的最小正奇数和最大负奇数.然后把大于0的都加起来,如果是奇数则输出,否则输出max(sum-最小正奇数,sum+最大负奇数).
#include<cstdio>
using namespace std;
const int inf=1e9;
int main()
{
int n;
int sum=0;
int minn=1e9;
int maxx=-1e9;
scanf("%d",&n);
while(n--){
int t;
scanf("%d",&t);
if(t>0)
sum += t;
if(t>0 && t%2 && minn>t)
minn=t;
if(t<0 && t%2 && maxx<t)
maxx=t;
}
if(sum%2)
printf("%d\n",sum);
else
printf("%d\n",max(sum+maxx,sum-minn));
}
滚动数组原理 :
这里用了滚动数组的原理,只要当前状态的决定量某些特定值位置有关,比如只与上一个状态量,左边或右边的状
态量,就可以用到滚动数组. 我们使每一次操作仅保留若干有用信息，新的元素不断循环刷新，看上去数组的空
间被滚动地利用，此模型我们称其为滚动数组. 滚动数组的优势是大大节省空间. //并且可以依次类推.
3 : LCS模板最长公共子序列
const int maxn=1e6;
char a[maxn],b[maxn];
int dp[2][maxn]; //只用两行是为了节省空间,因为每个判断都只有两种状态!
//这里就用了滚动数组,因为当前状态量只由上一个状态量或左边的状态量有关,所以就可以用到二维滚动数组.
int LCS(){
scanf("%s",a+1);
scanf("%s",b+1);
int len1=strlen(a+1);
int len2=strlen(b+1);
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(a[i] == b[j]) dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
else dp[i%2][j] = max(dp[i%2][j-1],dp[(i-1)%2][j]);
}
}
return dp[len1%2][len2];
}
模板题
POJ --- 1159 点这里 这也是一道求LCS的题,但是你不一定看的出来用LCS来做,因为这里只有一个串,所以我们需要转换下视角,那就是把一个串倒着看,不就有两个串了吗? 这样这两个串的LCS不就是最长的回文串吗?所以学聪明点啊!
4 : LIS 最长上升子序列(O(n^2)算法)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1005;
int a[maxn];
int maxlen[maxn]; //maxlen[k]表示存放以ak作为"终点"的最长上升子序列的长度.
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
maxlen[i]=1;
}
for(int i=2;i<=n;i++){ //每次求以第i个数为终点的最长上升子序列的长度.
for(int j=1;j < i;j++){ //查看以第j个数为起点的最长上升子序列的长度.
if(a[i] > a[j]) //把每一个都找一遍,则最后一定可以找到更长的.接下来更新就是了.
maxlen[i] = max(maxlen[i],maxlen[j]+1); //然后更新时,因为是从第一个开始找过来的.
} //所以maxnlen[i] 可能大于 maxlen[j]+1 所以取两者中较大的那个.
}
sort(maxlen,maxlen+n+1); //然后排个序,输出最大的那个值即可.
printf("%d\n",maxlen[n]);
}
再附上一个算法时间为nlogN的算法(比如POJ---3903 链接在此 就只能用这个算法才能A,上面那个算法会T)(且知道最长上升子序列为多少,如果有多个相等的最长上升子序列,则len数组中存的是总和最小的那个最长上升子序列)]
O(n*logn算法)
//logN在于用了二分查找.
//logN在于用了二分查找.
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int len[maxn]; //len[x] = y 表示所有长度为x时的最长上升子序列中末尾最小的那个序列中的最后那个数为y. 有点像贪心.
int lenth; //即找出来的最长上升子序列的总和是所有最长上升子序列中的最小的那个.
int BinaryFind(int x)
{
int l=1,r=lenth;
while(l<=r){
int mid=(l+r)>>1;
if(x<len[mid]) r=mid-1;
else if(x==len[mid]) break; //以后写二分都要加这个语句了(因为加了这个语句后,左边和右边的情况就可以随意写了).
else l=mid+1; //说明更大,所以长度要加长.
}
return l; //返回长度.
}
int main()
{
int n; //二分去找比当前长度的最后那个数还更大的那个数.
while(scanf("%d",&n)!=EOF){
lenth=0;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=n;i++){
int k=BinaryFind(a[i]); //更新长度.
len[k]=a[i];
lenth=max(lenth,k); //要最大的那个长度.
}
cout << lenth << endl;
for(int i=1;i<=5;i++)
printf("%d ",len[i]);
}
}
HDU --- 1025 点这里 这个也是一道变形LIS题,且数据范围比较大,要用NlogN的算法来做,否则会T,关键是你能否转换成来求LIS！只要这点想到了,这道题就是一个水题!!!
想提醒的是不要认为一定是给了什么字符串才想到用这些算法去做,而是也有许多变形题,思维要开阔,不要形成定式思维.!!!
5 : LCIS 最长公共上升子序列
int dp[maxn];
int LCIS(int n, int m)
{
memset(dp, 0, sizeof(dp));
for(int i=1;i<=n;i++){
int tmp=0;
for(int j=1;j<=m;j++){
if(a[i]>b[j] && dp[j]>tmp) //以两个串中短的那个作为基准.
tmp = dp[j]; //当前上升的最大长度.
else if(a[i]==b[j])
dp[j]=tmp+1; //为了如果当前相等的话就可以使最长的长度加一加.
}
}
int ans = 0;
for(int i = 1; i <= m; i++)
ans = max(ans, dp[i]);
return ans;
}
6 ： 最长公共子串
int dp[maxn][maxn];
int LCSTR(int n, int m)
{
int res=-1;
memset(dp, 0, sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i] == b[j]){
dp[i][j] = dp[i-1][j-1] + 1 ; //由状态转移方程可知,可以用滚动数组来做.(即第一维只用开 2 )
res = max(res,dp[i][j]);
}
else
dp[i][j] = 0; //因为是子串,所以在不等时直接清零,而不再是子序列中的去最优.
}
}
return res;
}
7 ： 最大子矩阵和
思想 : 动态规划
状态dp[i][j]代表长i宽j的矩阵的元素和。
（dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]）
假设要求找出x长y宽的最大子矩阵
在i>=x且j>=y的矩阵中找的话，
dp[i][j]就是包含a[i][j]元素的子矩阵的元素和，
则dp[i][j]-dp[i][j-y]-dp[i-x][j]+dp[i-x][j-y]就是
dp[i][j]中x长y宽的子矩阵的元素和（右下角元素为a[i][j]）
然后暴力循环比较一遍即可.复杂度 O(n^2).
int dp[maxn][maxn];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&dp[i][j]);
dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j- 1]; //减去多加了的那部分.
if(i>=x&&j>=y)
maxx = max(maxx,dp[i][j]-dp[i][j-y]-dp[i-x][j]+dp[i-x][j-y]); //每次都判的右下角那个矩阵.画个图就懂了.
}
}
8 : 最小正序列和(O(n^2)) 直接暴力 (不过网上也有NlogN的算法,相对于比较麻烦)
for (int i = 0; i != N; ++i) {
ThisSum = 0;
for (int j = i; j != N; ++j) {
ThisSum += A[j];
if (MinSum > ThisSum && ThisSum > 0)
MinSum = ThisSum;
}
}
9 : 最大子序列乘积
思想 :
遍历数组中每一个数 :
I : a[n] > 0 (或者有精度问题)
pos[n] = max{pos[n-1] * a[n], a[n]}
max_value = max{max_value, pos[n]}
若n-1位置存在最小负数, 更新 nag[n] = nag[n-1] * a[n]
II : a[n] < 0
pos[n] = max{nag[n-1] * a[n], 0.0}
max_value = max{max_value, pos[n]}
更新 nag[n] = min{pos[n-1] * a[n], a[n]}
III : a[n] ==0:
清空 nag[n] 与 pos[n]
const double eps=1e-6;
int MAX(int *a,int n) //如果有精度问题,则把有关的int改为double就行.
{
int maxx=0,pos=0,old=0,nag=1;
for(int i=0;i<n;i++){
if(a[i]>0){
pos = max(old * a[i] , a[i]);
maxx = max(maxx,pos);
if(nag<0)//如果nag还是大于0,则保持这样才可能是最后答案变大.否则乘a[i]后是nag更小,这样它乘负数时才可能使答案变更大. //其实这一步就是整个程序中最为关键的一步!!!
nag*=a[i];
}
else if(a[i]<0){
pos = max(0,nag*a[i]);
maxx = max(maxx,pos);
nag = (old * a[i] > a[i]) ? a[i] : old * a[i] ; //nag保存着最小的那个数.
}
old = maxx ; //保证两个数之间最大值可以连续,所以需要把上一个的最大值保存下来,才能有最大的答案.
}
return maxx;
}
