最大子序列:

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

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

#include 
     
      #define MAXN 8int 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
      
        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\n",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 
     
      #include 
      
       #define MAXN 500int 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
       
         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
        
          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\n",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