This is my code. I tried the test cases from the algorithmist site which seems to give me correct answer.But i am getting WA after submission:
- Code: Select all
#include<iostream>
using namespace std;
void Get_Max_Sum(int **array_2d,int row_sum[],int row2_sum[],int col_sum[],int col2_sum[],int size);
int main(void)
{
int **array_2d, i , j , size;
int max_sum(0);
int *row_sum,*col_sum,*row2_sum,*col2_sum;
while(cin >> size)
{
array_2d = new int*[size];
row_sum = new int[size];
col_sum = new int[size];
row2_sum = new int[size];
col2_sum = new int[size];
for(i = 0 ; i < size; ++i)
{
*(array_2d + i) = new int[size];
row_sum[i] = 0;
for(j = 0 ; j < size ; ++j)
{
cin >> *(*(array_2d + i) + j);
row_sum[i] += *(*(array_2d + i) + j);
}
row2_sum[i] = row_sum[i];
}
for(int i = 0 ; i < size ; ++i)
{
col_sum[i] = 0;
for(int j = 0 ; j < size ; ++j)
{
col_sum[i] += *(*(array_2d + j) + i);
}
col2_sum[i] = col_sum[i];
}
Get_Max_Sum(array_2d , row_sum ,row2_sum , col_sum , col2_sum, size);
delete(*array_2d);
delete(row_sum);
delete(col_sum);
delete(row2_sum);
delete(col2_sum);
}
return 0;
}
void Get_Max_Sum(int **array_2d,int row_sum[],int row2_sum[],int col_sum[],int col2_sum[],int size)
{
int row(0),col1(0),col2(0);
int real_sum(array_2d[0][0]);
int sum(0);
col2 = col1 + 1;
while(row < size && col1 < size - 1)
{
if(col2 == 1)
sum = array_2d[row][col1] + array_2d[row][col2] ;
else
sum += array_2d[row][col2];
if(real_sum < sum)
real_sum = sum;
if(col2 < size - 1)
{
++col2;
}
else
{
for(int i = row + 1 ; i < size ; ++i)
{
sum += row_sum[i];
if(real_sum < sum)
real_sum = sum;
}
++col1;
col2 = col1 + 1;
for(int i = 0 ; i < size ; ++i)
row_sum[i] = row2_sum[i] - array_2d[i][col1 - 1];
sum = 0;
}
if(col1 >= size - 1)
{
++row;
col1 = 0;
col2 = col1 + 1;
for(int i = 0 ; i < size ; ++i)
row2_sum[i] = row_sum[i];
}
}
int col(0),row1(0),row2(0);
sum = 0;
row2 = row1 + 1;
while(col < size && row1 < size - 1)
{
if(row2 == (row1 + 1) )
sum = array_2d[row1][col] + array_2d[row2][col] ;
else
sum += array_2d[row2][col];
if(real_sum < sum)
real_sum = sum;
if(row2 < size - 1)
{
++row2;
}
else
{
for(int i = col + 1 ; i < size ; ++i)
{
sum += col2_sum[i];
if(real_sum < sum)
real_sum = sum;
}
++row1;
row2 = row1 + 1;
for(int i = 0 ; i < size ; ++i)
col2_sum[i] = col2_sum[i] - array_2d[row1 - 1][i];
sum = 0;
}
if(row1 >= size - 1)
{
++col;
row1 = 0;
row2 = row1 + 1;
for(int i = 0 ; i < size ; ++i)
col2_sum[i] = col_sum[i];
}
}
cout << real_sum << endl;
}
Thanks in Advance.