问题描述:这个题目的意思很简单,有一个举证A[n][n],要从这个矩阵中找到一个子矩阵(至少为1×1),使得这个子矩阵的各项相加值最大。
从网上找了一下算法,用动态规划来做它是很确定的,参考了一位老兄的博客,写的很详细,也很容易理解,大家想看看可以点击上一行的“动态规划”,已经设置好链接。
这个题目首先要从一位的说起:
有 A1 A2 A3……An项,我们要求其一个字列,使得这个字列各项之和最大??
方法:1.遍历,计算出所有的可能性,这无疑是效率最低的一种方法,O(n^3);
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
{
int temp ;
for(int k=i;k<=j;k++)
temp =+ A[k];
sum=sum>temp?sum:temp;
}
2.利用已有的计算结果可以减少一重for 循环,O(n^2)
for(int i=0;i<n;i++) {
int temp ;
for(int j=i;j<n;j++)
{
temp=+A[j];
sum=sum>temp?sum:temp;
}
}
3.利用动态规划的处理,复杂度为O(n),空间复杂度也为O(n);
int sum = -1000 , temp = 0;
for(int i=0;i<n;i++)
{
if( temp >0) temp =+ A[i];
else temp = A[i];
sum=sum>temp?sum:temp;
}
注意第三种方法,动态规划。因为在后面二维矩阵中将他推广一下。
A11 A12 A13. . . . . . . . . A1n
A21 A22 A23. . . . . . . . . .A2n
. . . . . . . . . . . . . . .. . . . . .. . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
An1 An2 An3 . . . . . . . . . .Ann
上面是一个n*n的矩阵,现在要求它的最大子矩阵。
我们考虑这样一个数列[Ai1+..+Aj1 , Ai2+..+Aj2, Ai3..+Aj3 , Ai4..+ Aj4, .... , Ain...+ Ajn ],很熟悉。
上面这个数列的最大子序列便可以使用动态规划来求出。
到底有多少个这样的呢?? 这时我们关注一列,从第一列到第n列,一列n个数字[1,2,.......n] , 从中截取[i,...j];
我们用两个for循环便可以解决截取的问题。最终程序代码贴在下面
#include<iostream>
#include<cstdlib>
#define max 105
int array[max][max];
using namespace std ;
int SubMax(int n,int* p)
{
int sum = -1000 ;
int u = 0 ;
for(int i=0;i<n;i++)
{
if(u<0) u = p[i];
else u = p[i]+ u ;
sum=u>sum?u:sum;
}
return sum ;
}
int main()
{
int number;
int sum = -1000;
cin>>number;
if(number==1)
{
cin>>number;
cout<<number<<endl;
}
else {
for(int i=0;i<number;i++)
for(int j=0;j<number;j++)
cin>>array[i][j];
int*point = new int[number];
for(int i=0;i<number;i++)
{
for(int s=0;s<number;s++) //每次移动i后,对数组进行初始化
point[s]=0;
for(int j=i;j<number;j++)
{
for(int k=0;k<number;k++)
point[k]=point[k]+array[j][k];
int temp=SubMax(number,point);
sum = sum>temp?sum:temp;
}
}
cout<<sum <<endl;
}
system(“pause”);
return 0 ;
}
|
阅读(696) | 评论(0) | 转发(1) |