2.7: Tìm đường chạy dài nhất

 

Để xác định đường chạy dài nhất trong một mảng, ta có thể sử dụng một thuật toán duyệt mảng tuyến tính. Dưới đây là một phương pháp giải quyết bài toán của bạn:

1. Duyệt qua từng phần tử của mảng, bắt đầu từ vị trí đầu tiên.
2. Nếu phần tử hiện tại lớn hơn hoặc bằng phần tử trước đó, tăng biến đếm lên một.
3. Nếu không, so sánh độ dài đường chạy hiện tại với độ dài đường chạy lớn nhất đã tìm được. Nếu đường chạy hiện tại dài hơn, cập nhật vị trí bắt đầu và độ dài của đường chạy lớn nhất.
4. Lặp lại quá trình cho đến khi duyệt hết mảng.
5. Trả về vị trí bắt đầu và độ dài của đường chạy dài nhất.

Dưới đây là một ví dụ về cách triển khai thuật toán này trong Java:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Nhập mảng từ bàn phím
        System.out.print("Nhập số phần tử của mảng: ");
        int n = scanner.nextInt();
        int[] arr = new int[n];
        System.out.println("Nhập các phần tử của mảng:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        // Tìm đường chạy dài nhất
        int maxStartIndex = 0; // Vị trí bắt đầu của đường chạy dài nhất
        int maxLength = 1; // Độ dài của đường chạy dài nhất
        int currentStartIndex = 0; // Vị trí bắt đầu của đường chạy hiện tại
        int currentLength = 1; // Độ dài của đường chạy hiện tại

        for (int i = 1; i < n; i++) {
            if (arr[i] >= arr[i - 1]) {
                currentLength++;
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                    maxStartIndex = currentStartIndex;
                }
            } else {
                currentStartIndex = i;
                currentLength = 1;
            }
        }

        // In ra vị trí bắt đầu và độ dài của đường chạy dài nhất
        System.out.println("Vị trí bắt đầu của đường chạy dài nhất: " + maxStartIndex);
        System.out.println("Độ dài của đường chạy dài nhất: " + maxLength);

        scanner.close();
    }
}

Trong chương trình này:

• Chúng ta duyệt qua mảng và sử dụng các biến currentStartIndex và currentLength để theo dõi đường chạy hiện tại.
• Nếu phần tử hiện tại lớn hơn hoặc bằng phần tử trước đó, chúng ta tăng độ dài của đường chạy hiện tại lên một. Nếu không, chúng ta cập nhật currentStartIndex và currentLength cho đường chạy mới bắt đầu.
• Mỗi khi chúng ta kết thúc một đường chạy, chúng ta so sánh độ dài của nó với độ dài của đường chạy dài nhất đã tìm được cho đến thời điểm đó, và cập nhật các biến tương ứng nếu cần.
• Cuối cùng, chúng ta in ra vị trí bắt đầu và độ dài của đường chạy dài nhất.

Chúng ta đã thay đổi điều kiện so sánh từ arr[i] >= arr[i - 1] sang arr[i] <= arr[i - 1] để tìm đường chạy ngắn nhất.