输入描述
输入第一行为一个 NN 表示矩阵的行数和列数。接下来有 N 行，每行 N 个数，代表矩阵的元素. 1≤N≤80 , 并且每一个元素都在 [-127, 127] 的区间中
输出描述
最大子矩阵的和
样例输入
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出
15
#include <iostream>
using namespace std;
int ** a;
int **sum;
int max_array(int *a,int n)
{
int *c = new int [n];
int i =0;
c[0] = a[0];
for(i=1;i<n;i++)
{
if(c[i-1]<0)
c[i] = a[i];
else
c[i] = c[i-1]+a[i];
}
int max_sum = -65536;
for(i=0;i<n;i++)
if(c[i]>max_sum)
max_sum = c[i];
delete []c;
return max_sum;
}
int max_matrix(int n)
{
int i =0;
int j = 0;
int max_sum = -65535;
int * b = new int [n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
b[j]= 0;
for(j=i;j<n;j++)
{
for(int k =0;k<=n;k++)
b[k] += a[j][k];
int sum = max_array(b,n);
if(sum > max_sum)
max_sum = sum;
}
}
delete []b;
return max_sum;
}
int main()
{
int n;
cin >> n;
a = new int *[n];
sum = new int *[n];
int i =0;
int j =0;
for(i=0;i<n;i++)
{
sum[i] = new int[n];
a[i] = new int[n];
for(j=0;j<n;j++)
{
cin>>a[i][j];
sum[i][j] =0 ;
}
}
cout << max_matrix(n);
}
大概看了下
int * b = new int [n];
下面
for(int k =0;k<=n;k++)
b[k] += a[j][k];
也就是会访问到b[n]，这显然越界了
修改为
int * b = new int [n+1];
多组输入
int main()
{
while (1)
{
int n;
cin >> n;
if (n<=0) break; //输入0退出
a = new int *[n];
sum = new int *[n];
int i =0;
int j =0;
for(i=0;i<n;i++)
{
sum[i] = new int[n];
a[i] = new int[n];
for(j=0;j<n;j++)
{
cin>>a[i][j];
sum[i][j] =0 ;
}
}
cout << max_matrix(n);
}
}