Как найти длину самой длинной отсортированной подпоследовательности

Question

Учитывая последовательность целых чисел и печатает длину самой длинной отсортированной подпоследовательности. Если имеется более чем одна подпоследовательность равной максимальной длины, то подпоследовательность, которая появляется первой (одна с наименьшим индексом), должна использоваться для вывода

Для последовательности: 8 2 3 4 5 6 0 10 26 24 . Максимальная длина равна 5. Вот код, который у меня есть. Спасибо вам, ребята. Примечание: я не могу использовать массив. Я должен использовать Ctrl + Z, чтобы отобразить максимальную отсортированную длину подпоследовательности.

import java.io.IOException; 

public class RepeatingCharacterPositions { 
    public static void main(String[] s) throws IOException { 
     int counter = 0; 
     int inputValue; 
     int previousNum = 0; 
     int nextNum; 
     while ((inputValue = System.in.read()) != -1) { 
      nextNum = (int) inputValue; 
      if (previousNum < nextNum) { 
       counter++; 
      } else if (previousNum > nextNum) { 
       continue; 
      } 
      previousNum = nextNum; 
     } 
     System.out.println("Number of repeating " + counter); 
    } 
} 

Answer 1

Я считаю, что вам не хватает несколько вещей.

• Вы должны помнить максимальное значение вашего counter достигло
• Для того, чтобы получить int от System.in, вы должны использовать Scanner, который обеспечивает метод Scanner#nextInt
• Если две последующие цифры одинаковы , Я думаю, что они ARE приказал. Ваш тест должен быть if (previousNum <= nextNum)
• Если данное число меньше, чем предыдущий, вы должны «сбросить» counter к значению (потому что любое количество само по себе является упорядоченная последовательность из длины 1)

Например:

public static void main(final String[] s) { 
    int counter = 0; 
    int highestCount = 0; 
    int previousNum = 0; 
    int position = 0; 
    int latestStartingPosition = 0; 
    int startingPosition = 0; 

    int inputValue; 
    try (final Scanner sc = new Scanner(System.in)) { 
     while ((inputValue = sc.nextInt()) != -1) { 
      if (previousNum <= inputValue) { 
       counter++; 
       if (counter > highestCount) { 
        highestCount = counter; 
        startingPosition = latestStartingPosition; 
       } 
      } else { 
       latestStartingPosition = position; 
       counter = 1; 
      } 

      previousNum = inputValue; 
      position++; 
     } 
    } 

    System.out.println("starting pos: " + startingPosition); 
    System.out.println("Number of repeating positions: " + highestCount); 
} 

Я надеюсь, что это помогает!

---

EDIT: Ответ на дополнительный вопрос, заданный в комментариях.
Чтобы получить индекс начала длинной упорядоченной последовательности, вы должны:

• имеют int знать текущее положение в любой момент
• есть ссылка на исходную позицию последний вы столкнулись - это значение изменяется каждый раз, когда вы сбрасываете ваш основной counter.
• , когда вы обнаружили, что последовательность больше, чем любой другой вы когда-либо было раньше, то в исходное положение этой последовательности должно быть окончательное исходное положение: просто сохранить, что информация в любое время сохранить максимальное значение ваш counter достиг.

Смотрите обновленный пример в коде выше :)

Answer 2

Несколько замечаний:

1. Ваш продолжить пункт избавляет от установки previousNum = nextNum.
2. Возможно, вам необходимо сбросить счетчик, если найдете уменьшающееся число. Это означает, что вам также, вероятно, потребуется вторая переменная, которая отслеживает самую длинную последовательность, которую вы нашли.

3. Вы не обрабатываете два последовательных равных значения, по крайней мере, неявно. Вы должны рассмотреть возможность использования a> = или < = в зависимости от того, какой из ваших тестов имеет смысл.

   if (previousNum < nextNum) 
       { 
        counter++; 
       } 
       else if (previousNum > nextNum) 
       { 
        if(counter > longestSeq) 
        { 
         longestSeq = counter; 
        } 
        counter = 1; 
       } 
   
       previousNum = nextNum; 
   

Answer 3

Кроме того, что ccjmne отметили, вы всегда можете использовать отдельный метод, чтобы сделать это:

public class RepeatingCharacterPositions { 
    public static int findLongestSorted(int[] array) { 
     int maxCount = 0, count = 0; 
     int prev = array[0]; 
     for(int num : array) { 
      if(prev <= num) { 
       count++; 
      } else { 
       count = 1; 
      } 
      if(count > maxCount) 
       maxCount = count; 
      prev = num; 
     } 
     return maxCount; 
    } 

    public static void main(String[] s) throws IOException { 
     int[] arr = {8, 2, 3, 4, 5, 6, 0, 10, 26, 24}; 
     System.out.println("Number of repeating positions " + findLongestSorted(arr)); 
    } 
} 

Обратите внимание, что prev инициализируется быть первый элемент массива, поскольку массив с одним элементом считается отсортированным. После выполнения программы, она будет печатать

Number of repeating positions 5 

Если тест на массиве с одним элементом, например,

int[] arr = {8}; 

Это выход:

Number of repeating positions 1