CareerCup

Could you please explain the question? Do you mean 'find sub matrix with maximum sum of its elements' of all the possible sub-matrices of the given matrix?

//Problem:
//================
//find maximum sum of matrix.


//Example:
//================
//a[i][j]


//i=0-SIZE
//j=0-SIZE

//1-23
//45-6
//789

//Result=1+3+4+5+7+8+9

//ALGO:
//================

//Keep on adding in the sum if( Negative Numbers ) then dont add else add.

//TEST CASES:
//================
//FUNCTIONAL

//1. All negative numbers
//3. all positive numbers
//4. all 32767 int value integers
//5. Characters

//N.FUNCTIONAL
//Perf
//1. Keep on passing the same Data[Time to execute should be same]
//Stress
//2. Test with large N*n matrix and see if there is no failure or degradation
//Security:
//3. Test with non valid integers \1 \2
//Globalisation
//4. Test with Kanji characjters[japanese] and unicode
//5. Test with a mix of integers and characters
//6. Test With Mix of Unicode and Special characters


//TEST HARNESS:
//================

using System;

namespace Problem
{
public class Solution
{
static void Main()
{
int X = Convert.ToInt16(Console.ReadLine());
int Y = Convert.ToInt16(Console.ReadLine());
int[][] Array = new int[X][]; //Declaring an 2D array X element



for (int i = 0; i < X; i++)
{
Array[i] = new int[Y]; //Declaring an 2D array Y element
for (int j = 0; j < Y; j++)
{
Random R = new Random(4);
int Random = R.Next(0, 9);
Array[i][j] = Random;
}
}


Console.WriteLine(MaxArraySum(Array));
Console.ReadLine();

}



//CODE:
//================

public static int MaxArraySum(int[][] A)
{
int Sum = 0;
int RowLen = A[0].Length;
int ColumnLen = A.Length;

for (int i = 0; i < RowLen; i++)
{
for (int j = 0; j < ColumnLen; j++)
{

if (A[i][j] > 0)
Sum += A[i][j];
}
}
return Sum;
}
}
}



//ORDER:
//================
//O(N^2)

Yes, indeed, the most practical is O(n^3) solution which is explained well here artofproblemsolving.com/Forum/viewtopic.php?t=39544