检查子序列时循环后的重复条件

Question

当我检查子序列时，我总是在循环后复制条件。

例如，我想找出相差不超过1的数的最大子序列。这是我的代码

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

我复制条件是因为如果序列以匹配的子序列结尾，那么如果没有附加条件就不会被计算在内。我想避免代码重复。

我的解决方案需要更改输入。有什么方法可以在不改变输入的情况下避免代码重复。

将代码从条件转移到函数的解决方案不适合，因为它没有消除重复，我仍然需要调用函数两次。

Answer 1

此类问题的一般模式是使用两个“指针”（实际上是列表中的索引）：

一个“开始”指针，当它指向不属于子序列的元素时递增，直到到达列表的末尾，或者它指向子序列中的第一个元素（在特定在问题的情况下，没有不属于子序列的元素。
一个“结束”指针，最初等于开始（或比开始多一个），你递增它直到你到达列表的末尾，或者它指向第一个不属于列表的元素相同的子序列
你的子序列在开始和结束之间，分别包含和排除。根据需要进行处理
重复循环，起点等于上一个终点，直到到达列表末尾

所以，类似于：

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;
}

Answer 2

另一种使用 map 和 stream 解决它的方法

public static List<Integer> maxSubsequence(List<Integer> array) {

    Map<Integer, List<Integer>> result = new HashMap<>();
    List<Integer> firstArray = new ArrayList<>();
    firstArray.add(array.get(0));
    result.put(1, firstArray);
    for (int i = 0; i < array.size() - 1; i++) {
        if (Math.abs(array.get(i) - array.get(i + 1)) <= 1) {
            result.get(result.size()).add(array.get(i + 1));
        } else {
            firstArray = new ArrayList<>();
            firstArray.add(array.get(i + 1));
            result.put(result.size() + 1, firstArray);
        }
    }

    return result.values().stream().max(Comparator.comparingInt(List::size))
            .orElse(null); // add filter if you do not want to return and arraylist of single element like this .filter(ar -> ar.size() != 1)
}

检查子序列时循环后的重复条件

Duplicate condition after loop when checking subsequences

java

code-duplication