Tìm tổng con lớn nhất trong mảng số nguyên với Kadane Algorithm

Thuật toán Kadane là một thuật toán nổi tiếng để tìm tổng con lớn nhất của một mảng số nguyên. Thuật toán này hoạt động trong thời gian O(n) và rất hiệu quả cho bài toán này.

Dưới đây là triển khai chi tiết của thuật toán Kadane trong C#:

using System;

class Program
{
    // Hàm để tìm tổng con lớn nhất của một mảng số nguyên sử dụng thuật toán Kadane
    static int Kadane(int[] arr)
    {
        int maxSoFar = arr[0];
        int maxEndingHere = arr[0];

        for (int i = 1; i < arr.Length; i++)
        {
            // Tìm tổng lớn nhất của đoạn kết thúc tại vị trí i
            maxEndingHere = Math.Max(arr[i], maxEndingHere + arr[i]);

            // Cập nhật tổng lớn nhất toàn cục
            maxSoFar = Math.Max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }

    static void Main()
    {
        Console.WriteLine("Nhập vào các phần tử của mảng, cách nhau bởi dấu cách:");
        string input = Console.ReadLine();
        int[] arr = Array.ConvertAll(input.Split(' '), int.Parse);

        int maxSum = Kadane(arr);

        Console.WriteLine($"Tổng con lớn nhất của mảng là: {maxSum}");
    }
}

Giải thích chi tiết:

1. Kadane Method:

   • Tham số:
     • arr: Mảng số nguyên cần tìm tổng con lớn nhất.
   • Biến:
     • maxSoFar: Lưu trữ tổng lớn nhất toàn cục.
     • maxEndingHere: Lưu trữ tổng lớn nhất của đoạn kết thúc tại vị trí hiện tại.
   • Thuật toán:
     • Khởi tạo maxSoFar và maxEndingHere bằng phần tử đầu tiên của mảng.
     • Duyệt qua mảng từ vị trí thứ hai đến cuối:
       • Tính tổng lớn nhất của đoạn kết thúc tại vị trí hiện tại bằng cách lấy giá trị lớn hơn giữa phần tử hiện tại và tổng của đoạn kết thúc tại vị trí trước cộng với phần tử hiện tại.
       • Cập nhật tổng lớn nhất toàn cục nếu maxEndingHere lớn hơn maxSoFar.

2. Main Method:

   • Đọc mảng số nguyên từ người dùng, tách các phần tử bởi dấu cách và chuyển đổi thành mảng số nguyên.
   • Gọi hàm Kadane để tìm tổng con lớn nhất và in ra kết quả.

Ví dụ:

Giả sử bạn nhập vào mảng: -2 1 -3 4 -1 2 1 -5 4, chương trình sẽ in ra tổng con lớn nhất là 6, đoạn con này là [4, -1, 2, 1].

Phương pháp trên rất hiệu quả cho việc tìm tổng con lớn nhất trong một mảng số nguyên, và nó sử dụng không gian bộ nhớ O(1) ngoài mảng đầu vào. Bạn có thể chạy và thử nghiệm chương trình để hiểu rõ hơn về cách thức hoạt động của thuật toán Kadane.