Задача о возрастающей подпоследовательности

@Tomcio · Регистрация: 23.09.2018

Студворк — интернет-сервис помощи студентам

Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность. Напишите программу на языке Python, пожалуйста.

@dondublon · 28.02.2019, 13:11

Задача на динамическое программирование.

Обозначим требуемое решение для последовательности А через МВП(А). (МВП = максимальная возрастающая последовательность. Максимальная, потому что выкинули наименьшее возможное число элементов.)
Если А уже возрастающая, то решение для А найдено.
Если нет, тогда можно записать:
МВП(А)=самая_длинная_последовательность_ из(МВП(А-an[i]) для i=0..len(A))
Где (А-an[i])= подпоследовательность, из A без i-го элемента. То есть выкидываем по очереди все и берём максимальную из по результатам из оставшихся.

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

@m0nte-cr1st0 · 28.02.2019, 13:46

Tomcio,

Python
1
2
3
4
5
6
7
8
9
10
11
N = [3, 1, 6, 8 ,9, -1, 1, 0, 19]
 
i = 1
 
while i < len(N):
  if N[i-1] < N[i]: i += 1
  else: N.remove(N[i])
 
print(N)
 
#[3, 6, 8, 9, 19]

@dondublon · 28.02.2019, 15:27

m0nte-cr1st0, к сожалению, неверно.
К примеру, N = [6, 1, 3, 4, 9, -1, 1, 0, 19] даст результат [6, 9, 19]. Правильный ответ (оставшаяся последовательность) - [3 4 9 19].

Добавлено через 12 минут
Задача разбирается вот тут https://habr.com/ru/post/113108/ (Задача 4), правда, они её как-то по-другому решают, не вникал.

Добавлено через 3 минуты
А, ну да, припоминаю. В умной книжке написано, что такие задачи можно решать с начала (восходящая рекурсия) и с конца (нисходящая). Я предложил с конца, а они начали с начала. Наверное, их способ лучше - проще кеширование прикрутить.

Добавлено через 3 минуты
В копилочку https://ru.wikipedia.org/wiki/... 1%82%D0%B8

@m0nte-cr1st0 · 28.02.2019, 15:34

dondublon, можно ведь перебором сделать, меняя начальный индекс и сравнивая длины списков.

Добавлено через 59 секунд

Сообщение от dondublon

К примеру, N = [6, 1, 3, 4, 9, -1, 1, 0, 19] даст результат [6, 9, 19]. Правильный ответ (оставшаяся последовательность) - [3 4 9 19].

[1 3 4 9 19]?

@dondublon · 28.02.2019, 15:50

m0nte-cr1st0, конечно. "Правильный" ответ я на глаз привёл

"Перебор" - понятие растяжимое.

@m0nte-cr1st0 · 28.02.2019, 16:27

dondublon,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
X = [6, 1, 3, 4, 9, -1, 1, 0, 19]
 
L = []
M = []
j = 1
 
while j < len(X):
  i = j
  N = X[:]
  while i < len(N)-1:
    if N[i] < N[i+1]: 
      M.append(N[i])
      i += 1
    else:
      N.pop(i+1)
      
  j+=1
  if len(L) < len(M):
    L = M
  M=[]
 
if X[-1] > L[-1]:
  L.append(X[-1])
  
if X[0] < L[0]:
  L.insert(0, X[0])
  
print(L)
 
#[1, 3, 4, 9, 19]

@dondublon · 28.02.2019, 17:49

m0nte-cr1st0, вы решили поиграть со мной в игру "найди контрпример"?
Ну извольте

Этому вашему решению я подал X = [6, 7, 8, 9, 10, 3, -3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16, 17, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Решение выдаёт [-3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16] : 11 (11 - это длина).
Правильный ответ X1 =[ -3, -2, -1, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], длина 15.

Добавлено через 3 минуты
Если что, моё решение:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import numpy as np
 
def is_inc(sequence):
    return np.all(np.diff(sequence) > 0)
 
def max_inc(sequence):
    if is_inc(sequence):
        return sequence
 
    subs = [np.delete(sequence, i) for i in range(len(sequence))]
 
    results_sub = [max_inc(sub) for sub in subs]
    result = max(results_sub, key=lambda s: len(s))
    return result
 
# seq = np.array([4,5,6,0,1,7,2,8])
seq = np.array([3, 1, 6, 8 ,9, -1, 1, 0, 19])
print(max_inc(seq))

Оно без кеширования, тут над ним отдельно думать надо.

@m0nte-cr1st0 · 28.02.2019, 18:22

[/PYTHON]

Сообщение от dondublon

Этому вашему решению я подал X = [6, 7, 8, 9, 10, 3, -3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16, 17, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Решение выдаёт [-3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16] : 11 (11 - это длина).
Правильный ответ X1 =[ -3, -2, -1, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], длина 15.

это всё фиксится. было бы желание и время. не охота ещё сильней костыль увеличивать)

Добавлено через 15 секунд
[/PYTHON]

Сообщение от dondublon

Этому вашему решению я подал X = [6, 7, 8, 9, 10, 3, -3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16, 17, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Решение выдаёт [-3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16] : 11 (11 - это длина).
Правильный ответ X1 =[ -3, -2, -1, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], длина 15.

это всё фиксится. было бы желание и время. не охота ещё сильней костыль увеличивать)

@dondublon · 28.02.2019, 18:34

m0nte-cr1st0, жаль, число костылей обязано быть конечным

@Вадим Тукаев · 01.03.2019, 08:41

Пока Вы тут мерялись костылями, я написал просто, как по учебнику.

Кстати, буду благодарен, если кто-то расскажет, как там прикрутить кэширование. Я помню, в свое время читал в учебнике, что есть более эффективный способ, но тогда я это место пропустил, потому что мне и этот способ казался волшебством.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from random import randint
 
n = 10
a = [randint(1, 9) for _ in range(n)]
print(a)
 
 
b = [1] * n
for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            b[i] = max(b[i], b[j] + 1)
 
print(n - max(b))

@dondublon · 01.03.2019, 11:51

Вадим Тукаев, что это было, Беррримор?
На случайно сгенерённой, по предложению автора, последовательности [5, 3, 1, 3, 7, 7, 8, 2, 9, 7] оно выдало 5. Что это за 5? Бог весть.

На моей последовательности [3, 1, 6, 8 ,9, -1, 1, 0, 19] оно просто упало с index out of range.

PS. Видимо, это заразно - пытаться решить задачи на ДП без ДП. По учебнику - не надо так пытаться.

@Dirt2846 · 24.02.2024, 22:11

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    const N = Number(lines[0]);
    const NUMS = lines[1].split(' ').map(Number);
    const LIS = Array.from({length: N}, () => 1);
    const SEQUENCES = Array.from({length: N}, (_, i) => [NUMS[i]]);
 
    for (let i = N - 1; i >= 0; i--) {
        for (let j = i + 1; j < N; j++) {
            if (NUMS[i] < NUMS[j]) {
                if (LIS[i] < 1 + LIS[j]) {
                    LIS[i] = 1 + LIS[j];
                    SEQUENCES[i] = [NUMS[i], ...SEQUENCES[j]];
                }
            }
        }
    }
 
    const SORTED = SEQUENCES.sort((a, b) => b.length - a.length);
 
    return SORTED[0]; // вернет НВП

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
   
    const N = Number(lines[0]);
    const NUMS = lines[1].split(' ').map(Number);
    const LIS = Array.from({length: N}, () => 1);
 
    for (let i = N - 1; i >= 0; i--) {
        for (let j = i + 1; j < N; j++) {
            if (NUMS[i] < NUMS[j]) {
                LIS[i] = Math.max(LIS[i], 1 + LIS[j]);
            }
        }
    }
 
    return Math.max(...LIS); // вернет максимальную длину НВП

Решение на python с разбором здесь

@palva · 25.02.2024, 02:01

Сообщение от Dirt2846

Решение на python с разбором здесь

На русском здесь https://youtu.be/m4HOkVeN4Mo?s... N9V&t=3564

Добавлено через 2 часа 19 минут
Ой-ой-ой, зачем же я эту ссылку выложил! Хирьянов написал там неправильный код, да еще и не брался вычислять саму последовательность, а вернул только длину. Придется теперь мне за свою ссылку писать работу над ошибками.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def lis(A):
    F = [0] * len(A)
    F[0] = 1
    for  i in range(1, len(A)):
        m = 0
        for j in range(0, i):
            if A[i] > A[j] and F[j] > m:
                m = F[j]
        F[i] = m + 1
    return max(F)       
 
A = [6, 7, 8, 9, 10, 3, -3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16, 17, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(lis(A)) # 14

Добавлено через 28 минут
А вот с вычислением самой последовательности.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def lis(A):
    F = [1] * len(A)
    D = [-1] * len(A)
    
    for  i in range(1, len(A)):
        m = 0
        for j in range(0, i):
            if A[i] > A[j] and F[j] > m:
                m = F[j]
                D[i] = j
        F[i] = m + 1
    S = []
    ind = F.index(max(F))
    while ind != -1:
        S.append(A[ind])
        ind = D[ind]
    S.reverse()
    return S
 
A = [6, 7, 8, 9, 10, 3, -3, -2, -1, 4, 10, 11, 12, 13, 14, 15, 16, 17, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
S = lis(A)
print(S, len(S), sep=', ') # [-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 14

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@Tomcio 0 / 0 / 0 Регистрация: 23.09.2018 Сообщений: 10

	Задача о возрастающей подпоследовательности 28.02.2019, 12:59. Показов 29589. Ответов 13 Метки нет (Все метки) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность. Напишите программу на языке Python, пожалуйста. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	28.02.2019, 13:11
	Задача на динамическое программирование. Обозначим требуемое решение для последовательности А через МВП(А). (МВП = максимальная возрастающая последовательность. Максимальная, потому что выкинули наименьшее возможное число элементов.) Если А уже возрастающая, то решение для А найдено. Если нет, тогда можно записать: МВП(А)=самая_длинная_последовательность_ из(МВП(А-an[i]) для i=0..len(A)) Где (А-an[i])= подпоследовательность, из A без i-го элемента. То есть выкидываем по очереди все и берём максимальную из по результатам из оставшихся. Плюс не забыть прикрутить кеширование, иначе будет многократно вычисяться МВП для одних и тех же последовательностей. 1

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	28.02.2019, 15:27
	m0nte-cr1st0, к сожалению, неверно. К примеру, N = [6, 1, 3, 4, 9, -1, 1, 0, 19] даст результат [6, 9, 19]. Правильный ответ (оставшаяся последовательность) - [3 4 9 19]. Добавлено через 12 минут Задача разбирается вот тут https://habr.com/ru/post/113108/ (Задача 4), правда, они её как-то по-другому решают, не вникал. Добавлено через 3 минуты А, ну да, припоминаю. В умной книжке написано, что такие задачи можно решать с начала (восходящая рекурсия) и с конца (нисходящая). Я предложил с конца, а они начали с начала. Наверное, их способ лучше - проще кеширование прикрутить. Добавлено через 3 минуты В копилочку https://ru.wikipedia.org/wiki/... 1%82%D0%B8 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	28.02.2019, 15:50
	m0nte-cr1st0, конечно. "Правильный" ответ я на глаз привёл "Перебор" - понятие растяжимое. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	28.02.2019, 18:34
	m0nte-cr1st0, жаль, число костылей обязано быть конечным 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	01.03.2019, 11:51
	Вадим Тукаев, что это было, Беррримор? На случайно сгенерённой, по предложению автора, последовательности [5, 3, 1, 3, 7, 7, 8, 2, 9, 7] оно выдало 5. Что это за 5? Бог весть. На моей последовательности [3, 1, 6, 8 ,9, -1, 1, 0, 19] оно просто упало с index out of range. PS. Видимо, это заразно - пытаться решить задачи на ДП без ДП. По учебнику - не надо так пытаться. 0