Уникальная сортировка, как это реализовать

Question

Рахул нашел новый и уникальный способ сортировки массивов.

Если массив не отсортирован, он удалит первую или вторую половину массива и продолжит выполнение этого процесса, если массив полностью отсортирован.

Ваша задача - найти самый большой отсортированный массив, который можно получить из данного несортированного массива.

Answer 1

Вы можете просто использовать подход сортировки слиянием не для сортировки массива, а для поиска отсортированного массива, рекурсивно удаляя первую половину и вторую половину. Вот код, dry запустите его, и вы его получите.

  import java.util.*;
  import java.io.*;
  
  public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        while (tc-- > 0) {
            int n = sc.nextInt();
            int arr[] = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            boolean flag = true;
            for (int i = 0; i < n - 1; i++) {
                if (arr[i] <= arr[i + 1]) {
                    continue;
                } else {
                    flag = false;
                }
            }

            if (flag) {
                System.out.println(n);
            } else {
                int left = 0;
                int right = n - 1;
                int counter[] = new int[1];
                mergeSort(arr, left, right, counter);
                System.out.println(counter[0]+1);
            }

        }
    }

    static void mergeSort(int arr[], int left, int right, int counter[]) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, counter);
            mergeSort(arr, mid + 1, right, counter);
            merge(arr, left, mid, right, counter);
        }
    }

    static void merge(int arr[], int left, int mid, int right, int counter[]) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            R[i] = arr[mid + i + 1];
        }

        int i = 0, j = 0, counter1 = 0;

        while (i < n1 - 1) {
            if (L[i] <= L[i + 1]) {
                i++;
                counter1++;
            } else {
                break;
            }
        }
        if (counter1 + 1 == n1) {
            if (counter1 > counter[0]) {
                counter[0] = counter1;
            }
        }

        int counter2 = 0;
        while (j < n2 - 1) {
            if (R[j] <= R[j + 1]) {
                j++;
                counter2++;
            
            } else {

                break;
            }

        }
        if(counter2+1 == n2) {
            if (counter2 > counter[0]) {
                counter[0] = counter2;
            }
        }
    }
  }