最大子序列和最大子矩阵

最大子序列:

问题描述:给定整数序列:a1,a2,a3,...an(可能有负数),求a1~an的一个子序列ai~aj,使其和最大

　　我们很容易得到一个O(n^2)的暴力算法，但是注意到,每次在对s求和时,可能遇到部分和小于0,这样的话,显然应该舍弃前面的部分和序列,重新置s=0,并继续扫描下一个数,显然,s保存了前面的结果,这实际上是重复子问题,蕴含着有动态规划的思想,复杂度为O(n)

#include <stdio.h>
#define MAXN 8

int res_s,res_g,res;

void SubSum(int *a){
	int tmp = 0;
	int s,i;
	res_s = res_g = 0;
	s = 0;
	res = a[0];
	for(i=0;i<MAXN;i++){
		tmp += a[i];
		if(tmp > res){
			res = tmp;
			if(s != res_s) res_s = s; 
			res_g = i;
		}
		if(tmp < 0){
			tmp = 0; //舍弃前面的序列
			s = i+1;
		}
	}
	printf("[%d,%d]=%d
",res_s,res_g,res);
}

int main(){
	int a[MAXN]={4,-3,-4,8,-5,7,-5,7};
	SubSum(a);
	return 0;
}

 最大子矩阵:

问题描述:给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。其中，A的子矩阵指在A中行和列均连续的一块。

思路:m<n时,固定第i列到第j列的范围(否则固定第i到j行)，寻找在这个范围内的最大子矩阵，即把每行第i列上的元素到第j列的元素分别求和(下一行有对上一行的累加)，就转变为了一维的情况。由于有C(m,2)种列的组合，而求一维的子序列需要n的时间，所以，总体上时间复杂度为O(n*m*m)。图解如下:

//最大子矩阵 
#include <stdio.h>
#include <string.h>
#define MAXN 500

int n,m;
int res_s,res_g,res_s1,res_g1;
int res;
int M[MAXN][MAXN],b[MAXN];

void Input(){
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++){
			scanf("%d",&M[i][j]);
		}
}

int SubSum(int *b, int n, int *tmp_s, int *tmp_g){
	int tmp,res_,i,s;
	tmp = 0,res_ = b[0];
	s = *tmp_s = *tmp_g = 0;
	for(i=0;i<n;i++){
		tmp += b[i];
		if(tmp > res_){
			res_ = tmp;
			if(s != *tmp_s) *tmp_s = s;
			*tmp_g = i;
		}
		if(tmp < 0){
			tmp = 0; //舍弃前面的序列
			s = i+1;
		}
	}
	return res_;
}

void SubMatrix(){
	int flag,min_,max_;
	int i,j,t;
	n > m ? (flag=1,min_=m,max_=n) : (flag=0,min_=n,max_=m);
	res_s = res_g = res_s1 = res_g1 = 0;
	res = M[0][0]; //
	for(i=0;i<min_;i++){
		memset(b,0,sizeof(b));
		for(j=i;j<min_;j++){
			for(t=0;t<max_;t++){
				if(flag) b[t] += M[t][j]; //以行为主 
				else b[t] += M[j][t];
			}
			int tmp_s,tmp_g;  //以行为主时充当最大子序列的起始行,否则为起始列 
			int tmp = SubSum(b,max_,&tmp_s,&tmp_g);
			if(tmp > res){
				res = tmp;
				
				if(flag){
					if(tmp_s != res_s) res_s = tmp_s;
					if(i != res_g) res_g = i;
					res_s1 = tmp_g, res_g1 = j;
				}
				else{
					if(i != res_s) res_s = i;
					if(tmp_s != res_g) res_g = tmp_s;
					res_s1 = j, res_g1 = tmp_g;
				}
			}
		}
	}
	printf("[(%d,%d),(%d,%d)]=%d
",res_s,res_g,res_s1,res_g1,res);
}

int main(){
	int r;
	scanf("%d",&r); 
	while(r--){
		Input();
		SubMatrix();
	}
	return 0;
}

给两处最大子矩阵的问题链接:最大和,历届试题-最大子阵

　　2017-03-20 18:02:40