319
【算法小總結】最大連續子序列和最大連續子矩陣的關係與實現
最大連續子序列和最大連續子矩陣的關係與實現
求最長連續子序列的優化方法（非DP）
//求最大連續子序列和與對應的開頭元素和結束元素
實現代碼：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<limits.h>
#define MAXN 100002
using namespace std;
int main()
{
int i,j,n,a[MAXN],Max,sum,max;
int ps,pe,ts,te;//記錄開頭元素和結束元素
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sum=0;
Max=INT_MIN;
for(i=0;i<n;i++)
{
if(sum<=0)//如果序列和為負數，初始化sum與開始結束下標
{
sum=a[i];
ts=i;
te=i;
}
else//如果序列和為正數，繼續累加，並記錄新的結尾坐標
{
sum+=a[i];
te=i;
}
if(sum>Max)//一旦發現更大的連續子序列，就更新最大值和開始結束下標
{
Max=sum;
ps=ts;
pe=te;
}
}
printf("%d %d %d\n",Max,a[ps],a[pe]);
return 0;
}
例子：
8
1 -3 -5 2 6 -1 4 9
20 2 9
類似的是，在矩陣中求最大子矩陣的方法可以轉化成一維求最大連續子序列和的方法。
將矩陣的行或列壓縮。這裏我選擇列壓縮
如：
1 -1 2
4 9 15
-7 1 10
計算每一遞進行的最長連續子序列和，什麼是遞進行？舉個例子
全局變量MAX=-999999999
剛剛的矩陣
1 -1 2
4 9 15
-7 1 10
————————————————————————————————————
第一次記算取 1 -1 2
求出最長連續子序列是2，MAX=2
第二次取
1 -1 2
4 9 15
這裏兩行的每一列元素之和：5 8 17（從這裏開始就體現矩陣壓縮了）
求出最長連續子序列是30，MAX=30
第三次取
1 -1 2
4 9 15
-7 1 10
這裏三行的每一列元素之和：-2 9 27
求出最長連續子序列是36，MAX=36
————————————————————————————————————
第四次取：4 9 15
求出最長連續子序列是28，MAX=36
第五次取
4 9 15
-7 1 10
這裏兩行的每一列元素之和：-3 10 25
求出最長連續子序列是35，MAX=36
————————————————————————————————————
第六次次取：-7 1 10
求出最長連續子序列是11，MAX=36
————————————————————————————————————
到此為止，所有可能的子矩陣和全都計算完畢，得出最大的子矩陣元素之和為36
即是
-1 2
9 15
1 10
這個子矩陣
實現代碼：
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define MAXN 10002
int a[MAXN][MAXN],temp[MAXN];
int n;
int getsum()
{
int i,sum=0,max=0;
for(i=0;i<n;i++)
{
sum+=temp[i];
if(sum>max) max=sum;
if(sum<0) sum=0;
}
return max;
}
int main()
{
int i,j,ans,k;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
ans=INT_MIN;
for(i=0;i<n;i++)//從第i行開始
{
memset(temp,0,sizeof(temp));
for(j=i;j<n;j++)//從 i行到 n-1行都嚐試一次
{
for(k=0;k<n;k++)//把 j至 k行的每一列都加起來，就是矩陣壓縮
temp[k]+=a[j][k];
int pre=getsum();//計算壓縮矩陣形成的一維數組的最長連續序列
if(ans<pre)//更新最大值
ans=pre;
}
}
printf("%d\n",ans);
}
return 0;
}
剛剛的例子答案：
3
1 -1 2
4 9 15
-7 1 10
36
驗證方法無誤～
歡迎訪問程序員之洞https://blog.csdn.net/acmman/
最後更新：2017-04-03 05:39:54