Как получить наибольший возрастающий срез массива?

Question

Дано натуральное число N, далее следуют N целых чисел. Необходимо вывести в первой строке длину наибольшего среза. Со следующей строки вывести через пробел содержимое среза. Если таких срезов несколько, то выводить каждый из них с новой строки.

---

Sample Input:

7

2 1 2 3 1 5 7

---

Sample Output:

3

1 2 3

1 5 7

---

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

import java.util.Scanner;

public class TestClass {

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] a = new int[N];
        int d = 0;
        int e = 0;
        int f = 0;
        for (int i = 0; i < N; i++) {
            a[i] = in.nextInt();
        }
        for (int b = 0; b < N - 1; b++) {
            if (a[b] > a[b + 1]) {
                e++;
                if (e >= f) {
                    f = e;
                    e = 0;
                }
            } else if (a[b] < a[b + 1]) {
                e++;
            }
        }
        {
            e++;
            if (f <= e) {
                f = e;
            }
        }
        if (f == 0) {
            System.out.println(e);
        } else {
            System.out.println(f);
        }

        int k = 0;
        int[] g = new int[f - 1];
        for (int b = 0; b < N - 1; b++) {
            while (k < f) {
                g[k] = a[b];
                if (a[b] > a[b + 1]) {
                    k = f;
                    for (int v = 0; v < f - 1; v++) {
                        g[v] = 0;
                    }
                    k = 0;
                }
            }
            k++;
        }
    }
}

Answer 1

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

Создадим второй массив, в нем будем для каждого элемента i хранить его индекс в текущей подпоследовательности. Потом запомним длину самой большой подпоследовательности, и выведем все подпоследовательности этой длины.

Я не java не пишу вообще, но тут попробовал что то смастерить, если есть явные проблемы с кодом, то дайте мне знать.

Итак, код

public static void main(String[] args) {

    int[] input = new int[]{2, 1, 2, 3, 1, 5, 7};
    int[] lens = new int[input.length];

    int max = 0;

    for(int i=1; i<input.length; i++)
    {
        if (input[i]>input[i-1])
            lens[i] = lens[i-1]+1;
        else lens[i] = 0;
        max = Math.max(lens[i], max);
    }

    System.out.println(max + 1);

    for(int i=0; i<input.length; i++)
    {
        if (lens[i] == max)
        {
            for(int j=i-lens[i]; j<=i; j++)
                System.out.print(input[j] + " ");
            System.out.println();
        }
    }
}

На выходе получаем

3
1 2 3 
1 5 7 

Крайние случаи найдите и обработайте сами :)

Вариант со считыванием из консоли

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int N = in.nextInt();

    int[] input = new int[N];
    for(int i=0; i<N; i++) input[i] = in.nextInt();

    int[] lens = new int[input.length];

    int max = 0;

    for(int i=1; i<input.length; i++)
    {
        if (input[i]>input[i-1])
            lens[i] = lens[i-1]+1;
        else lens[i] = 0;
        max = Math.max(lens[i], max);
    }

    System.out.println(max + 1);

    for(int i=0; i<input.length; i++)
    {
        if (lens[i] == max)
        {
            for(int j=i-lens[i]; j<=i; j++)
                System.out.print(input[j] + " ");
            System.out.println();
        }
    }
}

Answer 2

Приведённый код ideone находит строго возрастающие непрерывные подмассивы (срезы) наибольшей длины и складывает их начальные индексы в список starts.

Строки из срезов длиной maxlen, начинающихся с этих индексов, я формировать не стал, думаю - это несложно.

    public static void main (String[] args) throws java.lang.Exception
    {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int[] a = new int[N];
    ArrayList starts = new ArrayList();
    int startcount = 0;
    for (int i = 0; i < N; i++) {
        a[i] = in.nextInt();
    }
    int start = 0;
    int maxlen = 0;
    for (int i = 1; i <= N; i++) {
        if (i == N || a[i] <= a[i - 1]) {
            if (i - start >= maxlen) {
                if (i - start > maxlen) {
                    maxlen = i - start;
                    starts.clear();
                }
                starts.add(start);
                start = i;
            }
        }    
    }        
    for (int i = 0; i < starts.size(); i++)
        System.out.println(starts.get(i));
}

Answer 3

Могу помочь с составлением алгоритма решения. Можете написать решение по нему или проверить свой на следование ему:

• Разбиваете вторую строку с числами с помощью string.split(sep)
• Превращаете массив строк в массив чисел
• Если в массиве больше одного элемента:
  • Создаете промежуточный список типа List
  • Создаете результирующий список
  • Сохраняете максимальную длину последовательности пока как ноль
  • Первый элемент добавляете в промежуточный список
  • Проходите в цикле по массиву с числами из последовательности, начиная со второго элемента
    • Если новый элемент больше старого:
      • Сохраняете его в промежуточный список
    • Иначе:
      • Копию промежуточного списка добавляете в результирующий
      • Если максимальная длина меньше размера промежуточного:
        • Максимальную длину приравниваете к размеру промежуточного
      • Промежуточный очищаете
      • Добавляете в промежуточный текущий элемент(который больше старого)
  • Кладёте текущий промежуточный список также в результирующий
  • Его длину также сравниваете с максимальной и переопределяете максимальную, если она меньше
  • В результирующем списке оставляете только те списки, длина которых равна максимальной
  • Выводите размер результирующего списка
  • Для каждого из его вложенных списков:
    • Выводите этот список в строковом представлении
• Иначе:
  • Печатаете единицу и сам первый элемент