Подсчет жизнеспособных длин подсписков из массива

Question

Это для функции пригодности генетического алгоритма, поэтому важно, чтобы я мог сделать это максимально эффективно, так как это будет повторяться снова и снова.

Допустим, есть функция foo (массив int []), которая возвращает истину, если массив является «хорошим» массивом, и ложь, если массив является «плохим» массивом. Что делает это хорошим или плохим, здесь не имеет значения. Это не та функция, которую мы здесь определяем. Это просто зависит от функции, которую я пытаюсь выяснить.

Учитывая полный массив [1,6,8,9,5,11,45,16,9], допустим, что подмассив [1,6,8] является «хорошим» массивом, как определено в foo () и [9,5,11,45] является «хорошим» массивом, как определено функцией foo (). Кроме того, [5,11,45,16,9] является «хорошим» массивом, а также самым длинным «хорошим» массивом. Обратите внимание, что хотя [9,5,11,45] является «хорошим» массивом, а [5,11,45,16,9] является «хорошим» массивом, [9,5,11,45,16,9 ] - «плохой» массив.

Обратите внимание, что это не функция foo (), которую мы определяем. Все, что нас беспокоит, это то, что мы берем все возможные подмассивы полного массива, отправляем их в foo (), определяем, хорошие они или плохие, и подсчитываем их длины. Единственная проблема заключается в том, что мы не хотим считать «хорошие» подмассивы «хороших» подмассивов, но есть «хорошие» подмассивы, которые могут начинаться внутри другого хорошего подмассива, но заканчиваться вне его.

Мы хотим, чтобы счетчики длины всех «хороших» массивов, а не подмассивов «хороших» массивов. Кроме того, как описано выше, «хороший» массив может начинаться в середине другого «хорошего» массива, но комбинация этих двух может быть «плохим» массивом.

Answer 1

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

В качестве параметров должны использоваться индексы начала и конца подмассива, проверьте, хорошо это или нет.

Если массив хорош, его индексы start и end должны храниться во внешней структуре. В противном случае вы должны сделать 2 рекурсивных вызова: от start index до end-1 index и от start+1 index до end index.

public void getLargestGoodArrays (int start, int end) {
   if (isGood (start, end) {
      saveGoodArray (start, end);
   } else {
      //here you should iterate through all already found good arrays to check whether the array with larger bounds already saved
      if (!isSubarrayOfGoodArray (start, end - 1)) {
         getLargestGoodArrays (start, end - 1);
      }
      if (!isSubarrayOfGoodArray (start + 1, end)) {
         getLargestGoodArrays (start + 1, end);
      }          
   }
}