Counting viable sublist lengths from an array.

Question

This is for a genetic algorithm fitness function, so it is important I can do this as efficiently as possible, as it will be repeated over and over.

Lets say there is a function foo(int[] array) that returns true if the array is a "good" array and false if the array is a "bad" array. What makes it good or bad does not matter here. This is not the function we are defining here. It is simply relied upon by the function I'm attempting to figure out.

Given the full array [1,6,8,9,5,11,45,16,9], lets say that subarray [1,6,8] is a "good" array as defined by foo() and [9,5,11,45] is a "good" array as defined by foo(). Furthermore [5,11,45,16,9] is a "good" array, and also the longest "good" subarray. Notice that while [9,5,11,45] is a "good" array, and [5,11,45,16,9] is a "good" array, [9,5,11,45,16,9] is a "bad" array.

Notice its not the foo() function we are defining. All we are concerned about is that we take all possible subarrays of the full array, send them to foo(), find if they are good or bad, and count their lengths. The only issue is that we don't want to count "good" subarrays of "good" subarrays, but there are "good" subarrays which might start within another good subarray, but end outside of it.

We want the length counts of all "good" arrays, but not subarrays of "good" arrays. Furthermore, as described above, a "good" array might begin in the middle of another "good" array, but the combination of the two might be a "bad" array.

Answer 1

You need a recursive algorithm which saves it's results to some external data structure.

It should take subarray start and end indexes as parameters, check whether it's good or not.

If the array is good then its start and end indexes should be stored in that external structure. Otherwise you should make 2 recursive calls: from start index to end-1 index and from start+1 index to 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);
      }          
   }
}