字符串中 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

。

另外，你的条件逻辑也有问题。仅当当前交替序列结束（即

arr[i] == arr[i+1]

）时才应到达 else 子句，但当当前序列不长于最大序列时也应到达。

因此，条件应分为两个条件：

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

Answer 2

int findSubArray(int arr[], int n) {
    if(n<=0){
        return 0;
    }
    int maxLen = 1;
    int prevPos = -1;
    for(int i=1;i<n;i++){
        maxLen = max(maxLen, i-1-prevPos);
        if(arr[i-1] == arr[i]){
            prevPos = i-1;
        }
    }
    maxLen = max(maxLen, n-1 - prevPos);
    return maxLen;
}

Answer 3

为什么不直接计算不同的相邻值并最后相加呢？就是这样。

count = 1

# Iterate through the list starting from the second element
for i in range(1, len(X)):
    # If the current element is different from the previous one, it's alternating
    if X[i] != X[i - 1]:
        count += 1

return count