## Amazon Interview Question

- 0of 0 votes
find maximum sum of 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)

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?

- sdm March 12, 2010