Duplicate condition after loop when checking subsequences

Question

When I check for subsequences I always duplicate the condition after the loop.

For example, I want to find the maximum subsequence of numbers with a difference of no more than one. Here is my code

public static List<Integer> maxSubsequence(List<Integer> array) {
    int ind = 0;
    int bestInd = 0;
    int cnt = 1;
    int maxCnt = 0;

    for(int i = 1; i < array.size(); i++) {
        if(Math.abs(array.get(ind) - array.get(i)) <= 1) {
            cnt++;
            continue;
        }

        if(cnt > maxCnt) {
            bestInd = ind;
            maxCnt = cnt;
        }

        if(Math.abs(array.get(ind) - array.get(i)) == 2) {
            cnt--;
            ind++;
            i--;
        } else {
            cnt = 1;
            ind = i;
        }
    }

    // duplicate from loop
    if(cnt > maxCnt) {
        bestInd = ind;
        maxCnt = cnt;
    }

    return array.subList(bestInd, bestInd + maxCnt);
}

for sequence 5, 1, 2, 3, 3, 3 answer is 2, 3, 3, 3

I am duplicating the condition because if the sequence ends with a matching subsequence, then it will not be counted without an additional condition. I would like to avoid code duplication.

My solution requires changing the input. Are there any ways to avoid code duplication without changing the input.

The solution with the transfer of the code from the condition to the function won't fit, since it does not eliminate duplication, I still need to call function twice.

Answer 1

The general pattern for such a question is to use two "pointers" (indexes into the list, really):

• A "start" pointer, which you increment while it points to elements which are not part of a subsequence, until you reach the end of the list, or it points to the first element in the subsequence (in the specific case of the problem in the question, there are no elements not part of a subsequence).
• An "end" pointer, initially equal to the start (or one more than the start), which you increment until either you hit the end of the list, or it's pointing to the first element which isn't part of the same subsequence
• Your subsequence is then between start and end, inclusive and exclusive respectively. Process it as necessary
• Repeat the loop with the start equal to the previous end, until you hit the end of the list

So, something like:

int start = 0;
while (start < list.size()) {
  // Increase end as much as you can for this subsequence
  int end = start + 1;
  while (end < list.size()) {
    if (/* condition meaning you don't want to increment end any more */) {
      break;
    }
    end++;
  }

  // See if this subsequence is "best"
  int cnt = end - start;
  if (cnt > maxCnt) {
    bestInd = start;
    maxCnt = cnt;
  }

  // Prepare for next iteration.
  start = end;
}