Самая большая чередующаяся подпоследовательность единиц и нулей в строке ⇐ JAVA

[Anonymous]

Найти наибольшую подпоследовательность из чередующихся 1 и 0 в строке, содержащую только 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.

В чем ошибка в приведенном выше коде? Кроме того, может помочь любой псевдокод для альтернативного подхода.

Подробнее здесь: https://stackoverflow.com/questions/488 ... n-a-string