using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public class Index 

    { 

        public int Row; 

        public int Col; 

    }   

    public class SubmatrixMaxSumOutput 

    {

        public int MaxSum;

        public List<Index> SubMatrixCoord;

    }   

    public static SubmatrixMaxSumOutput GetMaxSumInMatrix(int[,] arr)

    {

        int N = arr.GetLength(0); int M = arr.GetLength(1); // размеры матрицы

​

        // Изменим исходную матрицу посчитав частичные суммы по столбцам

        for (int j = 0; j < M; j++) {

            for (int i = 1; i < N; i++) {

                arr[i, j] += arr[i - 1, j];

            }

        }

​

        int maxSum = int.MinValue;

        List<Index> tempIndexes = new List<Index>(); List<Index> indexes = new List<Index>();

​

        // Фиксируем строки row1 и row2

        for (int row_1 = 0; row_1 < N; row_1++) { 

            for (int row_2 = row_1; row_2 < N; row_2++) {

​

                int partSum = 0; tempIndexes.Clear();

​

                // проходим по столбцам

                for (int k = 0; k < M; k++) 

                { 

                    // считаем частичную сумму и сохраняем индексы элементов

                    partSum += row_1 > 0 ? arr[row_2, k] - arr[row_1 - 1, k] : arr[row_2, k];

                    tempIndexes.Add(new Index { Row = row_1 + 1, Col = k + 1 });

                    tempIndexes.Add(new Index { Row = row_2 + 1, Col = k + 1 });

​

                    // нашли макс.частичную сумму - сохраняем и записываем координаты прямоугольника

                    if (partSum > maxSum) 

                    {

                        maxSum = partSum;

                        indexes.Clear(); indexes.AddRange(tempIndexes);

                    } 

                    if (partSum < 0)

                    {

                        partSum = 0;

                        tempIndexes.Clear();

                    }

                }

            }

        }

        return new SubmatrixMaxSumOutput { MaxSum = maxSum, SubMatrixCoord = indexes };

    }   

    public static void Main()

    {

        Console.WriteLine("UniLecs");

        int[,] arr = new int[,]

        {

            { -1, -2, -3 },

            {  1,  1, -4 },

            {  1,  1, -5 }

        };

        var output = GetMaxSumInMatrix(arr);

​

        // Вывод

        Console.WriteLine(string.Format("\nMax Sum = {0}", output.MaxSum)); 

        if (output.SubMatrixCoord.Count > 1) 

        {

            Index leftUpIndex = output.SubMatrixCoord.FirstOrDefault(); 

            Index rightDownIndex = output.SubMatrixCoord.LastOrDefault();

            Console.WriteLine(string.Format(

                "SubMatrix coordinates: ({0}, {1}) - ({2}, {3})\n",

                leftUpIndex.Row, leftUpIndex.Col, 

                rightDownIndex.Row, rightDownIndex.Col));

        }

    }

}