Найдите максимальную длину подмассива, где каждый элемент покрывает непрерывный диапазон целых чисел.

Question

У меня есть задача на Hackkerrank, как показано ниже

Рассмотрим массив из n цен на билеты, билеты. Число m определяется как размер некоторой подпоследовательности s билетов, каждый элемент которой покрывает непрерывный диапазон целых чисел. То есть, если бы вы отсортировали элементы в s, абсолютная разница между любыми элементами j и j + 1 была бы либо 0, либо 1. Определите максимальную длину подпоследовательности, выбранной из массива билетов.

Пример

билеты = [8, 5, 4, 8, 4]

Допустимые подпоследовательности, отсортированные, - это {4, 4, 5} и {8, 8}. Эти подпоследовательности имеют m значений 3 и 2 соответственно. Возврат 3.

Описание функции

Завершите функцию maxTickets в редакторе ниже.

maxTickets имеет следующие параметры:

int tickets[n]:  an array of integers

Возвращает

int:  an integer that denotes the maximum possible value of m

Ограничения

1 ≤ n ≤ 10^5
1 ≤ tickets[i] ≤ 10^9

Пример ввода 0

Функция STDIN

4 → билеты [] размер n = 4

4

13

2

3

Образец Выходные данные 0

3

Пояснение 0

Есть две подпоследовательности билетов, которые содержат последовательные целые числа при сортировке: {2, 3, 4} и {13}. Эти подпоследовательности имеют m значений, равных 3 и 1 соответственно. Верните максимальное значение m, равное 3.

И ниже мой код, но я не знаю, хорошее ли это решение для него

import java.util.*;

public class MaxTickets {

    public static void main(String[] args) {
        test(4,13,2,4,3);
        test(10,1,5,2,5,5,2,6,3,5,3);
        test(10,1,5,1,2,5,5,2,6,3,5,3);
        test(9,1,4,5,2,2,3,1,6,9,10);
        test(1,2,4,7,8,11,22);
        test(1,2,2,2,3,4,7,8,11,14,22);
        test(1,1,2,4,4,4,7,8,11,22);
    }

    static int maxTickets(List<Integer> tickets) {
        Collections.sort(tickets);
        tickets.forEach(num -> System.out.print(num + " "));

        List<Integer> list = new ArrayList<>();
        int len = tickets.size();
        int distance;
        int curDistance = Integer.MIN_VALUE;
        int lastDistance = Integer.MIN_VALUE;
        boolean first = true;

        for(int i = 1; i < len; i++) {
            int left = tickets.get(i-1);
            int right = tickets.get(i);
            distance = right - left;

            if(i == 1) {
                updateSum(list, 2);
            } else {
                if(lastDistance == 0 && first) {
                    updateSum(list, 1);
                }
                else if(distance == 0 ||
                    distance == curDistance) {
                    updateSum(list, 1);
                } else if(distance != curDistance) {
                    list.add(1);
                }
            }

            if(distance != 0) {
                curDistance = distance;
            }
            lastDistance = distance;
            if(i >= 2) {
                first = false;
            }
        }

        return
        list.stream()
            .max(Comparator.comparingInt(i  -> i))
            .get();

    }

    private static void updateSum(List<Integer> list, int value) {
        if(list.isEmpty()) {
            list.add(value);
        } else {
            int lastIndex = list.size() - 1;
            list.set(lastIndex, list.get(lastIndex) + value);
        }
    }

    private static void test(Integer... numbers) {
        List<Integer> list = Arrays.asList(numbers);
        int result = maxTickets(list);
        System.out.println("\n" + result);
    }

}

Вывод:

2 3 4 4 13 
4
1 2 2 3 3 5 5 5 5 6 10 
5
1 1 2 2 3 3 5 5 5 5 6 10 
6
1 1 2 2 3 4 5 6 9 9 10 
8
1 2 4 7 8 11 22 
2
1 2 2 2 3 4 7 8 11 14 22 
6
1 1 2 4 4 4 7 8 11 22 
3

Мой код работает? Есть ли случай, когда мой код не работает? Не могли бы вы предложить лучший алгоритм для этой задачи?

Answer 1

Самый простой (а также самый быстрый) способ решить эту проблему - это go для наиболее простого и понятного алгоритма. Вот псевдокод, описывающий это.

Function unbroken_range(arr) {
    n = arr.length;
    sorted_arr = sort(arr);
    range_start = 0;
    best_len = 0;
    for i from 1 to n-1:
        if sorted_arr[i] - sorted_arr[i-1] > 1 then {
            current_len = i - range_start;
            if current_len > best_len then {
                best_len = current_len;
            }
            range_start = i;
        }
    }
    return max(n - range_start, best_len);
}   

Судя по результатам, ваша программа выполняет свою работу. Я не go, хотя это подробно, но вы можете сравнить его с этим псевдокодом и посмотреть, похожа ли структура алгоритма (должна, это действительно самый простой способ справиться с этим imho).

Answer 2

Моя ошибка, я неправильно понимаю предложение «То есть, если бы вы отсортировали элементы в s, абсолютная разница между любыми элементами j и j + 1 была бы либо 0, либо 1».

Псевкод алгоритма ниже:

arr = sorted(arr)
ret = -1
cnt = 1
for i in range(1, len(arr)):
   if abs(arr[i] - arr[i-1]) > 1:
      ret = max(ret, cnt)
      cnt = 0
   else:
      cnt += 1
return max(ret,cnt)

Java Программа:

static int maxTickets(List<Integer> tickets) {
        Collections.sort(tickets);
        tickets.forEach(num -> System.out.print(num + " "));
        int ret = -1;
        int cnt = 1;
        int len = tickets.size();

        for (int i=1; i < len; i++) {
            if ( tickets.get(i) - tickets.get(i-1) > 1) {
                ret = Math.max(ret, cnt);
                cnt = 0;
            }
            else {
                cnt += 1;
            }
        }

        return Math.max(ret,cnt);
    }