Квадрат с максимальной суммой

Question

Я изучаю C #, и в настоящее время я делаю многомерные массивы.Я хочу написать программу, которая читает матрицу , а затем находит наибольшую сумму 2x2 подматрицы и печатает ее.

int[] dimensions = Console.ReadLine()
            .Split(", ", StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse)
            .ToArray();

int rows = dimensions[0];
int columns = dimensions[1];

int[,] matrix = new int[rows,columns];

for (int i = 0; i < rows; i++)
{
     int[] numbers = Console.ReadLine()
                .Split(", ", StringSplitOptions.RemoveEmptyEntries)
                .Select(int.Parse)
                .ToArray();

     for (int j = 0; j < columns; j++)
     {
          matrix[i, j] = numbers[j];
     }
 }

int maxSum = int.MinValue;
        int selectedRow = -1;
        int selectedCol = -1;

        for (int row = 0; row < matrix.GetLength(0) - 1; row++)
        {
            for (int col = 0; col < matrix.GetLength(1) - 1; col++)
            {
                int currentSum = matrix[row, col] + matrix[row, col + 1] + matrix[row + 1, col] + matrix[row + 1, col + 1];

                if (currentSum > maxSum)
                {
                    maxSum = currentSum;
                    selectedRow = row;
                    selectedCol = col;
                }

            }
        }

        Console.WriteLine($"{matrix[selectedRow, selectedCol]} {matrix[selectedRow, selectedCol + 1]}");
        Console.WriteLine($"{matrix[selectedRow + 1, selectedCol]} {matrix[selectedRow + 1, selectedCol + 1]}");
        Console.WriteLine(maxSum);

Итак, я прочитал матрицу, но я не уверен, как начать поиск подматриц и для сравнения их сумм .Я был бы очень признателен, если бы вы могли дать мне несколько советов.

Answer 1

Вам нужно проверить только значения current, под позициями ваших i и current, вправо позиций ваших j .

Я имею в виду, это будет проверяться так:

• [7,1] [1,3] [3,3]
• [1,3] [3,9] [9,8]

и т. Д.

После каждого сравнения рассчитайте сумму этой матрицы 2x2 и сохраните ее в словаре. Для возврата вам просто нужно найти максимальное значение ключа и получить значение этого ключа.

public class MatrixTest
    {
        public static IEnumerable<object[]> TestData =>
            new List<object[]>
            {
                new object[]
                {
                    new int[,]
                    {
                        {7, 1, 3, 3, 2, 1},
                        {1, 3, 9, 8, 5, 6},
                        {4, 6, 7, 9, 1, 0}
                    },
                    new int[,]
                    {
                        {9, 8},
                        {7, 9}
                    },
                    33
                },
                new object[]
                {
                    new int[,]
                    {
                        {10, 11, 12, 13},
                        {14, 15, 16, 17}
                    },
                    new int[,]
                    {
                        {12, 13},
                        {16, 17}
                    },
                    58
                }
            };


        [Theory]
        [MemberData(nameof(TestData))]
        public void Test(int[,] input, int[,] expectedArray, int expectedSum)
        {
            MatrixHandler m = new MatrixHandler();

            var resp = m.GetMax2x2Matrix(input);

            resp.Item1.Should().Be(expectedSum);

            resp.Item2.Should().BeEquivalentTo(expectedArray);
        }
    }


    public class MatrixHandler
    {
        public (int, int[,]) GetMax2x2Matrix(int[,] source)
        {
            var sumsPlusTempArrays = new Dictionary<int, int[,]>();

            int[,] temp;
            int sum = 0;

            for (int i = 0, n0 = source.GetLength(0) - 1; i <= n0; i++)
            {
                for (int j = 0, n1 = source.GetLength(1) - 1; j <= n1; j++)
                {
                    if (i + 1 <= n0 && j + 1 <= n1)
                    {
                        temp = new int[2,2];
                        temp[0, 0] = source[i, j];
                        temp[0, 1] = source[i, j + 1];
                        temp[1, 0] = source[i + 1, j];
                        temp[1, 1] = source[i + 1, j + 1];
                        sum = CalculateSum(temp);
                        sumsPlusTempArrays.TryAdd(sum, temp);
                    }
                }
            }

            var key = sumsPlusTempArrays.Select(x => x.Key).Max();

            var value = sumsPlusTempArrays[key];

            return (key, value);
        }

        private int CalculateSum(int[,] source)
        {
            int sum = 0;

            for (int i = 0, n0 = source.GetLength(0); i < n0; i++)
            {
                for (int j = 0, n1 =  source.GetLength(1); j < n1; j++)
                {
                    sum += source[i, j];
                }
            }
            return sum;
        }
    }