Member 13679031 Ответов: 2

Как найти наибольшую чередующуюся подпоследовательность 1s и 0s в строке

Найдите самую большую чередующуюся подпоследовательность 1s и 0s в строке, содержащей только 1s и 0s.также найдите начальный индекс для самой большой подпоследовательности

Пример для 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.

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

OriginalGriff

И что же?
Что он делает такого, чего вы не ожидали, или не делает того, что вы сделали?
Какие данные вы ему скормили?
Какие результаты вы получили?
Что вы пытались сделать, чтобы выяснить, почему он это делает?
Что же показывал отладчик происходящего?

2 Ответов

Рейтинг:
1

Patrice T

Когда вы не понимаете, что делает ваш код, ответ-отладчик.
эта линия выглядит подозрительно

if (arr[i] != arr[i+1] && maxsize < i - j + 1)

это мешает правильно найти вторую последовательность в:
int [] ia = {1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1}


Существует инструмент, который позволяет вам видеть, что делает ваш код, его имя отладчик Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Когда вы не понимаете, что делает ваш код или почему он делает то, что он делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик - Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010 - YouTube[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.

Рейтинг:
0

CPallini

Я бы написал:

static int findSubArray(int arr[])
{
  int max_size = -1, start_index = 0;
  int end_index = 0;
  int start_sequence=0;
  boolean in_sequence = false;

  int n = arr.length;

  for (int i = 0; i < n - 1; i++)
  {
    if ( in_sequence )
    {
      if ( arr[i] == arr[i+1])
      {
        in_sequence = false;
        if ( i - start_sequence >= max_size)
        {
          max_size = i -start_sequence + 1;
          start_index = start_sequence;
        }
      }
    }
    else
    {
      if ( arr[i] != arr[i+1] )
      {
        in_sequence = true;
        start_sequence = i;
      }
    }
  }
  if ( in_sequence )
  {
    if ( n - start_sequence > max_size)
    {
      max_size = n -start_sequence;
      start_index = start_sequence;
    }
  }

  end_index = start_index + max_size - 1;
  if (max_size == -1)
    System.out.println("No such subarray");
  else
    System.out.println(start_index + " to " + end_index);

  return max_size;
}