Tìm Ma Trận Con Có Tổng Lớn Nhất Trong C#

Để tìm ma trận con có tổng lớn nhất trong một ma trận hai chiều trong C#, bạn có thể sử dụng thuật toán Kadane hai chiều. Thuật toán này là sự mở rộng của thuật toán Kadane một chiều, được sử dụng để tìm mảng con có tổng lớn nhất.

Cách thực hiện:

1. Khởi tạo ma trận hai chiều.
2. Sử dụng thuật toán Kadane hai chiều để tìm ma trận con có tổng lớn nhất.

Dưới đây là mã nguồn minh họa:

using System;

class Program
{
    static void Main()
    {
        int[,] matrix = {
            { 1, 2, -1, -4, -20 },
            { -8, -3, 4, 2, 1 },
            { 3, 8, 10, 1, 3 },
            { -4, -1, 1, 7, -6 }
        };

        int rows = matrix.GetLength(0);
        int cols = matrix.GetLength(1);
        int maxSum = int.MinValue;
        int left = 0, right = 0, top = 0, bottom = 0;

        for (int leftCol = 0; leftCol < cols; leftCol++)
        {
            int[] temp = new int[rows];

            for (int rightCol = leftCol; rightCol < cols; rightCol++)
            {
                for (int i = 0; i < rows; i++)
                {
                    temp[i] += matrix[i, rightCol];
                }

                var kadaneResult = Kadane(temp);
                int currentSum = kadaneResult.Item1;
                int startRow = kadaneResult.Item2;
                int endRow = kadaneResult.Item3;

                if (currentSum > maxSum)
                {
                    maxSum = currentSum;
                    left = leftCol;
                    right = rightCol;
                    top = startRow;
                    bottom = endRow;
                }
            }
        }

        Console.WriteLine($"Ma trận con có tổng lớn nhất là: {maxSum}");
        Console.WriteLine($"Vị trí: Từ hàng {top} đến hàng {bottom}, từ cột {left} đến cột {right}");
    }

    static Tuple<int, int, int> Kadane(int[] array)
    {
        int maxSum = array[0], currentSum = array[0];
        int start = 0, end = 0, tempStart = 0;

        for (int i = 1; i < array.Length; i++)
        {
            if (currentSum + array[i] < array[i])
            {
                currentSum = array[i];
                tempStart = i;
            }
            else
            {
                currentSum += array[i];
            }

            if (currentSum > maxSum)
            {
                maxSum = currentSum;
                start = tempStart;
                end = i;
            }
        }

        return new Tuple<int, int, int>(maxSum, start, end);
    }
}

Giải thích:

• Khởi tạo ma trận hai chiều: Ma trận matrix được khởi tạo với các giá trị.
• Thuật toán Kadane hai chiều:
  • Biến temp: Mảng tạm thời để lưu tổng của các phần tử trong một dải cột.
  • Biến maxSum: Lưu tổng lớn nhất tìm được.
  • Các biến left, right, top, bottom: Lưu vị trí của ma trận con có tổng lớn nhất.
  • Vòng lặp leftCol và rightCol: Duyệt qua từng cặp cột để tính tổng của dải cột.
  • Hàm Kadane: Tìm mảng con có tổng lớn nhất trong dải cột hiện tại.
  • **Cập nhật maxSum và vị trí ma trận con nếu tổng hiện tại lớn hơn maxSum