Программа, кажется, всегда возвращает 1 для любого входа

Question

Я пытаюсь решить этот вопрос о конкурентном программировании под названием Thanos Sort. Для получения более подробной информации по этому вопросу, пожалуйста, нажмите на эту ссылку: https://codeforces.com/problemset/problem/1145/A Этот конкурс закончился очень долго go, поэтому обсуждение разрешено. Это кажется довольно простым вопросом. Я попытался решить вопрос с помощью рекурсии (повторное разбиение массива пополам и проверка его сортировки, и если я обнаружил, что одна из половин была отсортирована, я возвращаю значение длины половины). Вот мой код:

import java.util.*;
import java.io.*;
class Main {
 public static void main(String[] args) throws IOException{
   BufferedReader b1 = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(b1.readLine());
   for(int i = 0; i<T; i++) {
     String vals [] = (b1.readLine()).split(" ");
     int nums [] = new int[vals.length];
     for(int j = 0; j<vals.length; j++) {
         nums[j] = Integer.parseInt(vals[j]);
     }
     System.out.println(solve(nums));
   }
 }
 public static int solve(int arr[]) {
   int temp1 [] = new int[arr.length/2];
   int temp2 [] = new int[arr.length/2];
   for(int i = 0; i<arr.length/2; i++) {
     temp1[i] = arr[i];
   }
   for(int i = arr.length/2; i<arr.length; i++) {
     temp2[i-(arr.length/2)] = arr[i];
   }
   if(isSorted(temp1) == true) {
     return temp1.length;
   }
    if(isSorted(temp2) == true) {
     return temp2.length;
   }
   solve(temp1);
   solve(temp2);
  return 1;
 } 
 public static boolean isSorted(int [] arr) {
   for(int i = 0; i<arr.length; i++) {
     if(arr.length == 1) {
       return true;
     }
     if(i < arr.length-2 && arr[i] < arr[i+1]) {
       continue;
     }
     else {
       return false;
     }
   }
   return true;
 }
}

Мой код, кажется, всегда выводит 1, когда тестируется на любом массиве. Я понимаю, что у меня есть оператор «return 1» в конце моего кода (мне нужно иметь его там, так как другие операторы return находятся внутри if-операторов). Я считаю, что ошибка вызвана тем, что у меня есть «return 1» Есть предложения?

Answer 1

Когда вы выполняете рекурсию, вы отбрасываете значение, возвращаемое рекурсией. Измените

solve(temp1);
solve(temp2);
return 1;

на что-то вроде

return Math.max(1, Math.max(solve(temp1), solve(temp2)));

Кроме того, ваш isSorted алгоритм, похоже, не работает. Выполните итерацию массива, убедитесь, что каждое значение равно или больше предыдущего. Мол,

public static boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}