java - 字符串中 1 和 0 的最大交替子序列

Question

在仅包含 1 和 0 的 String 中查找最大的 1 和 0 交替子序列。还要找到最大子序列的起始索引。

示例:

对于1101011，最长的交替子序列长度为5，从索引1到5。

我尝试通过比较连续的元素来做到这一点，如果它们不相等，则将当前长度与最大大小进行比较:

int findSubArray(int arr[], int n) 
{
    int sum = 0;
    int maxsize = -1, startindex = 0;
    int endindex = 0;

    int j = 0;
    for (int i = 0; i < n - 1; i++)  {
        if (arr[i] != arr[i+1] && maxsize < i - j + 1) {
            maxsize = i - j + 1;
            startindex = j;
        } else {
            j = i;
        }
    }

    endindex = startindex+maxsize-1;
    if (maxsize == -1)
        System.out.println("No such subarray");
    else
        System.out.println(startindex+" to "+endindex);

    return maxsize;
}

测试方法:

int [] ia = {1, 1, 0, 1, 0, 1, 1};
findSubArray (ia, 7);

返回:5 并打印 0 到 4

问题是虽然它打印了正确的长度，即 5，但索引不正确。正确的输出应该是 1 到 5。

为了纠正这个问题，如果我执行 j = i + 1，那么整个匹配将进行一次折腾，我得到的索引为 0 到 0。

上面的代码有什么错误？此外，任何替代方法的伪代码都会有所帮助。

Answer 1

您将 j = i; 更改为 j = i + 1; 是正确的，但这还不够。

您缺少的是当前交替序列从 j 开始并在 i+1 结束，而不是 i。

另外，你的条件逻辑有问题。您的 else 子句应该仅在当前交替序列结束时到达(即 arr[i] == arr[i+1])，但当当前序列不长于最大值时也会到达顺序。

因此条件应该分为两个条件:

if (arr[i] != arr[i+1]) {
    if (maxsize < i + 1 - j + 1) {
        maxsize = i + 1 - j + 1;
        startindex = j;       
    }
} else {
    j = i + 1;
}