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

Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности

Задача

«Найти длину самой большой возрастающей подпоследовательности в массиве.»

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

На пальцах

Есть последовательность:

5, 10, 6, 12, 3, 24, 7, 8

Вот примеры подпоследовательностей:

10, 3, 8
5, 6, 3

А вот примеры возрастающих подпоследовательностей:

5, 6, 7, 8
3, 7, 8

А вот примеры возрастающих подпоследовательностей наибольшей длины:

5, 6, 12, 24
5, 6, 7, 8

Да, максимальных тоже может быть много, нас интересует лишь длина.
Здесь она равна 4.

Теперь когда задача определена, решать мы ее начинаем с (сюрприз!) вычисления чисел Фибоначчи, ибо вычисление их — это самый простой алгоритм, в котором используется “динамическое программирование”. ДП — термин, который лично у меня никаких правильных ассоциаций не вызывает, я бы назвал этот подход так — “Программирование с сохранением промежуточного результата этой же задачи, но меньшей размерности”. Если же посчитать числа Фибоначчи с помощью ДП для вас проще пареной репы — смело переходите к следующей части. Сами числа Фибоначчи не имеют отношения к исходной задаче о подпоследовательностях, я просто хочу показать принцип ДП.

Последовательность Фибоначчи O(n)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

Берем 0, прибавляем 1 — получаем 1.
Берем 1, прибавляем 1 — получаем 2.
Берем 1, прибавляем 2 — получаем, ну вы поняли, 3.

Собственно нахождение n-го элемента этой последовательности и будет нашей задачей. Решение кроется в самом определении этой последовательности. Мы заведем один мутабельный массив, в который будем сохранять промежуточные результаты вычисления чисел Фибоначчи, т.е. те самые n-1 и n-2.

Псевдокод:

int numberForIndex(int index) {

   int[] numbers = [0, 1]; // мутабельный массив, можем добавлять к нему элементы

    for (int i = 2; i < index + 1; i++) {
        numbers[index] = numbers[i - 1] + numbers[i - 2];
    }

    return numbers[index];
}

→ Пример решения на Objective-C

→ Тесты

Вот и всё, в этом массиве numbers вся соль ДП, это своего рода кэш (Caсhe), в который мы складываем предыдущие результаты вычисления этой же задачи, только на меньшей размерности (n-1 и n-2), что дает нам возможность за одно действие найти решение для размерности n.

Этот алгоритм работает за O(n), но использует немного дополнительной памяти — наш массив.

Вернемся к нахождению длины максимальной возрастающей подпоследовательности.

Решение за O( n ^ 2)

Рассмотрим следующую возрастающую подпоследовательность:

5, 6, 12

теперь взглянем на следующее число после последнего элемента в последовательности — это 3.

Может ли оно быть продолжением нашей последовательности? Нет. Оно меньше чем 12.

А 24 ?

Оно да, оно может.

Соответственно длина нашей последовательности равна теперь 3 + 1, а последовательность выглядит так:

5, 6, 12, 24

Вот где переиспользование предыдущих вычислений: мы знаем что у нас есть подпоследовательность 5, 6, 12, которая имеет длину 3 и теперь нам легко добавить к ней 24. Теперь у вас есть ощущение того, что мы можем это использовать, только как?

Давайте заведем еще один дополнительный массив (вот он наш cache, вот оно наше ДП), в котором будем хранить размер возрастающей подпоследовательности для n-го элемента.

Выглядеть это будет так:

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

“Что за загадочные i и j?” — спросите вы. Это индексы итераторов по массиву, которые мы будем использовать. Изменяться они будут с помощью двух циклов, один в другом. i всегда будет меньше чем j.

Сейчас j смотрит на 10 — это наш кандидат в члены последовательностей, которые идут до него. Посмотрим туда, где i, там стоит 5.

10 больше 5 и 1 <= 1, counts[j] <= counts[i]? Да, значит counts[j] = counts[i] + 1, помните наши рассуждения в начале?

Теперь таблица выглядит так.

Смещаем j.

Результат:

Имея перед глазами эту таблицу и понимая какие шаги нужно делать, мы теперь легко можем реализовать это в коде.

int longestIncreasingSubsequenceLength( int numbers[]  ) {

    if (numbers.count == 1) {
        return 1;
    }

   int lengthOfSubsequence[] = Аrray.newArrayOfSize(numbers.count, 1);

    for (int j = 1; j < numbers.count; j++) {
        for (int k = 0; k < j; k++) {
            if (numbers[j] > numbers[k]) {
                if (lengthOfSubsequence[j] <= lengthOfSubsequence[k]) {
                 lengthOfSubsequence[j] = lengthOfSubsequence[k] + 1;
                }
            }
        }
    }

    int maximum = 0;

    for (int length in lengthOfSubsequence) {
        maximum = MAX(maximum, length);
    }

    return maximum;
}

→ Реализация на Objective-C
→ Тесты

Вы не могли не заметить два вложенных цикла в коде, а там где есть два вложенных цикла проходящих по одному массиву, есть и квадратичная сложность O(n^2), что обычно не есть хорошо.

Теперь, если вы билингвал, вы несомненно зададитесь вопросом “Can we do better?”, обычные же смертные спросят “Могу ли я придумать алгоритм, который сделает это за меньшее время?”

Ответ: “да, можете!”

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

Бинарный поиск O(log n)

Бинарный поиск работает только на отсортированных массивах. Например, нам нужно найти позицию числа n в отсортированном массиве:
1, 5, 6, 8, 14, 15, 17, 20, 22

Зная что массив отсортирован, мы всегда можем сказать правее или левее определенного числа в массиве искомое число должно находиться.

Мы ищем позицию числа 8 в этом массиве. С какой стороны от середины массива оно будет находиться? 14 — это число в середине массива. 8 < 14 — следовательно 8 левее 14. Теперь нас больше не интересует правая часть массива, и мы можем ее отбросить и повторять ту же самую операцию вновь и вновь пока не наткнемся на 8. Как видите, нам даже не нужно проходить по всем элементам массива, сложность этого алгоритма < O( n ) и равна O (log n).

Для реализации алгоритма нам понадобятся 3 переменные для индексов: left, middle, right.

Ищем позицию числа 8.

Мы отгадали где находится 8 с трёх нот.

int binarySearch(int list [], int value) {

    if !list.isEmpty {
        int left = list.startIndex
        int right = list.endIndex-1

        while left <= right {

            let middle = left + (right - left)/2

            if list[middle] == value{
                return middle
            }

            if value < list[middle]{
                right = middle - 1
            }
            else{
                left = middle + 1
            }
        }
    }
    return nil
}

Решение за O (n * log n)

Теперь мы будем проходить по нашему исходному массиву при этом заполняя новый массив, в котором будет храниться возрастающая подпоследовательность. Еще один плюс этого алгоритма: он находит не только длину максимальной возрастающей подпоследовательности, но и саму подпоследовательность.

Как же двоичный поиск поможет нам в заполнении массива подпоследовательности?

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

Если элемент больше максимального элемента в массиве, добавляем элемент в конец. Это просто.

Если такой элемент уже существует в массиве, ничего особо не меняется. Это тоже просто.

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

Все это запутанно, сейчас будет проще, сведем к рассмотрению 2-х оставшихся случаев.

1. Рассматриваемый элемент последовательности (x) меньше чем наибольший элемент в массиве (Nmax), но больше чем предпоследний.
2. Рассматриваемый элемент меньше какого-то элемента в середине массива.

В случае 1 мы просто можем откинуть Nmax в массиве и поставим на его место x. Так как понятно, что если бы последующие элементы были бы больше чем Nmax, то они будут и больше чем x — соответственно мы не потеряем ни одного элемента.

Случай 2: для того чтобы этот случай был нам полезен, мы заведем еще один массив, в котором будем хранить размер подпоследовательности, в которой этот элемент является максимальным. Собственно этим размером и будет являться та позиция в первом вспомогательном массиве для этого элемента, которую мы найдем с помощью двоичного поиска. Когда мы найдем нужную позицию, мы проверим элемент справа от него и заменим на текущий, если текущий меньше (тут действует та же логика как и в первом случае)

Не расстраивайтесь, если не все стало понятно из этого текстового объяснения, сейчас я покажу все наглядно.

Нам нужны:

1. Исходная последовательность
2. Создаем мутабельный массив, где будем хранить возрастающие элементы для подпоследовательности
3. Создаем мутабельный массив размеров подпоследовательности, в которой рассматриваемый элемент является максимальным.

Результат:

int longestIncreasingSubsequenceLength(int numbers[]) {

    if (numbers.count <= 1) {
        return 1;
    }

    int lis_length = -1;

    int subsequence[];
    int indexes[];

    for (int i = 0; i < numbers.count; ++i) {
        subsequence[i] = INT_MAX;
        subsequence[i] = INT_MAX;
    }

    subsequence[0] = numbers[0];
    indexes[0] = 0;

    for (int i = 1; i < numbers.count; ++i) {
        indexes[i] = ceilIndex(subsequence, 0, i, numbers[i]);

        if (lis_length < indexes[i]) {
            lis_length = indexes[i];
        }
    }

    return lis_length + 1;
}

int ceilIndex(int subsequence[], 
              int startLeft, 
              int startRight,
              int key){

    int mid = 0;
    int left = startLeft;
    int right = startRight;
    int ceilIndex = 0;
    bool ceilIndexFound = false;

    for (mid = (left + right) / 2; left <= right && !ceilIndexFound; mid = (left + right) / 2) {
        if (subsequence[mid] > key) {
            right = mid - 1;
        }
        else if (subsequence[mid] == key) {
            ceilIndex = mid;
            ceilIndexFound = true;
        }
        else if (mid + 1 <= right && subsequence[mid + 1] >= key) {
            subsequence[mid + 1] = key;
            ceilIndex = mid + 1;
            ceilIndexFound = true;
        } else {
            left = mid + 1;
        }
    }

    if (!ceilIndexFound) {
        if (mid == left) {
            subsequence[mid] = key;
            ceilIndex = mid;
        }
        else {
            subsequence[mid + 1] = key;
            ceilIndex = mid + 1;
        }
    }

    return ceilIndex;
}

→ Реализация на Objective-C
→ Тесты

Итоги

Мы с вами сейчас рассмотрели 4 алгоритма разной сложности. Это сложности, с которыми вам приходится встречаться постоянно при анализе алгоритмов:

О( log n ), О( n ), О( n * log n ), О( n ^ 2 )

Эта картинка из вот этой статьи

Еще мы рассмотрели примеры использования Динамического Программирования, тем самым расширив наш инструмент разработки и понимания алгоритмов. Эти принципы пригодятся вам при изучении других проблем.

Для лучшего понимания я рекомендую вам закодировать эти проблемы самим на привычном вам языке. А еще было бы здорово, если бы вы запостили ссылку на ваше решение в комментах.

Еще предлагаю подумать над тем как доработать последний алгоритм за O (n * log n ) так чтобы вывести еще и саму наибольшую подпоследовательность. Ответ напишите в комментах.

Всем спасибо за внимание, до новых встреч!

Ссылки:
Вопрос на Stackoverflow.com
Примеры реализации на C++ и Java
Видео с объяснением

Решение за время O(N²)

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

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

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

vector<int> findLIS(vector<int> a):
   int n = a.size                     //размер исходной последовательности
   int prev[0..n - 1]
   int d[0..n - 1]
 
   for i = 0 to n - 1
       d[i] = 1
       prev[i] = -1
       for j = 0 to i - 1
           if (a[j] < a[i] and d[j] + 1 > d[i])
               d[i] = d[j] + 1
               prev[i] = j
 
   pos = 0                            // индекс последнего элемента НВП
   length = d[0]                      // длина НВП
   for i = 0 to n - 1
       if d[i] > length
           pos = i
           length = d[i]
   
   // восстановление ответа
   vector<int> answer
   while pos != -1
       answer.push_back(a[pos])
       pos = prev[pos]
   reverse(answer)
 
   return answer    

Решение за O(N log N)

Для более быстрого решения данной задачи построим следующую динамику: пусть — число, на которое оканчивается возрастающая последовательность длины , а если таких чисел несколько — то наименьшее из них. Изначально мы предполагаем, что , а все остальные элементы .
Заметим два важных свойства этой динамики: , для всех и каждый элемент обновляет максимум один элемент . Это означает, что при обработке очередного , мы можем за c помощью двоичного поиска в массиве найти первое число, которое больше либо равно текущего и обновить его.

Для восстановления ответа будем поддерживать заполнение двух массивов: и . В будем хранить индекс элемента, на который заканчивается оптимальная подпоследовательность длины , а в — позицию предыдущего элемента для .

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

vector<int> findLIS(vector<int> a):
   int n = a.size                     //размер исходной последовательности
   int d[0..n]
   int pos[0..n]
   int prev[0..n - 1]
   length = 0
   
   pos[0] = -1
   d[0] = -INF
   for i = 1 to n
       d[i] = INF
   for i = 0 to n - 1
       j = binary_search(d, a[i])
       if (d[j - 1] < a[i] and a[i] < d[j])
           d[j] = a[i]
           pos[j] = i
           prev[i] = pos[j - 1]
           length = max(length, j)
   
   // восстановление ответа
   vector<int> answer
   p = pos[length]
   while p != -1
       answer.push_back(a[p])
       p = prev[p]
   reverse(answer)
 
   return answer

Ещё одно решение за О(N log N)

Существует ещё одно решение, которое позволяет нам найти длину наибольшей возрастающей подпоследовательности, но без возможности восстановления данной подпоследовательности. Для этого мы воспользуемся таблом Юнга. Оно обладает таким свойством, что длина первой строки табла и будет являться искомой величиной^[1].

Само табло представляет из себя расположение различных целых чисел в массиве строк, выровненных по левому краю, где в строке содержится элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент , если он больше либо равен , где — длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент , который больше данного . Поставить элемент вместо . С элементом требуется провести те же действия, что и с , только уже на строке табла.

Пример построения табла на массиве  :

1. Берём элемент . Видим, что , который расположен на первой строке в ячейке с индексом . Увеличиваем и .

2. Берём элемент . Видим, что . Увеличиваем и .

3. Аналогично для элемента .

4. Берём элемент . Так как , то бинарным поиском находим нужную нам позицию , такую, что . В данном случае это
первая позиция. Присваиваем и проделываем такую же операцию, но для строки с индексом .

5. Аналогично для элемента .

6. Аналогично для элемента .

Таким образом, длина наибольшей возрастающей подпоследовательности для массива равна (например, подпоследовательность из элементов ).

См. также

• Задача о наибольшей общей подпоследовательности
• Наибольшая общая возрастающая подпоследовательность
• Задача о наибольшей общей палиндромной подпоследовательности

Примечания

Источники информации

• Википедия — Задача поиска наибольшей увеличивающейся подпоследовательности
• Wikipedia — Longest increasing subsequence
• Дистанционная подготовка — Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)
• MAXimal :: algo :: Длиннейшая возрастающая подпоследовательность за O (N log N)

Видимо я тут чего-то важного не понимаю.

#include <stdio.h>

struct range {
  int start, end;
};

// inclusive range
struct range
max_gtseq (int *a, int n)
{
  struct range result = {0, 0};
  int max = 0, start = 0, end = 0;

  for (int i = 0; i < n - 1; i++)
    if (a[i] < a[i + 1])
      end++;
    else {
      if (end - start > max) {
        max = end - start;
        result.start = start;
        result.end = end;
      }
      end = start = i + 1;
    }

  if ((n - 1) - start > max) {
    result.start = start;
    result.end = n - 1;
  }

  return result;
}

int
main (int ac, char *av[])
{
  int x[] = {1, 2, 3, 10, 1, 2, 100, 1, 2, 3, 4, 5, 6, 0}; //{10, 9, 8};

  struct range r = max_gtseq(x, sizeof(x) / sizeof(x[0]));

  printf ("start = %d end = %dn", r.start, r.end);

  return puts("End") == EOF;
}

Неужели такой тривиальный однопроходный алгоритм не работает?

What is a Subarray?

A subarray is a contiguous part of array, i.e., Subarray is an array that is inside another array.

In general, for an array of size n, there are n*(n+1)/2 non-empty subarrays.

For example, Consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays. The subarrays are:

(1), (2), (3), (4), 
(1,2), (2,3), (3,4), 
(1,2,3), (2,3,4), and 
(1,2,3,4)

What is a Subsequence?

A subsequence is a sequence that can be derived from another sequence by removing zero or more elements, without changing the order of the remaining elements.

More generally, we can say that for a sequence of size n, we can have (2ⁿ – 1) non-empty sub-sequences in total.

For the same above example, there are 15 sub-sequences. They are:

(1), (2), (3), (4), 
(1,2), (1,3),(1,4), (2,3), (2,4), (3,4), 
(1,2,3), (1,2,4), (1,3,4), (2,3,4), 
(1,2,3,4). 

What is a Subset?

If a Set has all its elements belonging to other sets, this set will be known as a subset of the other set.

A Subset is denoted as “⊆“. If set A is a subset of set B, it is represented as A ⊆ B.

For example, Let Set_A = {m, n, o, p, q}, Set_ B = {k, l, m, n, o, p, q, r}

Then, A ⊆ B.

Topics:

Problems on Subarray:

• Easy Problems on Subarray:
  1. Split an array into two equal Sum subarrays
  2. Check if subarray with given product exists in an array
  3. Subarray of size k with given sum
  4. Sort an array where a subarray of a sorted array is in reverse order
  5. Count subarrays with all elements greater than K
  6. Maximum length of the sub-array whose first and last elements are same
  7. Check whether an Array is Subarray of another Array
  8. Find array such that no subarray has xor zero or Y
  9. Maximum subsequence sum such that all elements are K distance apart
  10. Longest sub-array with maximum GCD
  11. Count of subarrays with sum at least K
  12. Length of Smallest subarray in range 1 to N with sum greater than a given value
  13. Sum of all subarrays of size K
  14. Split array into K disjoint subarrays such that sum of each subarray is odd.
  15. Find an array of size N having exactly K subarrays with sum S
  16. Find the subarray of size K with minimum XOR
  17. Length of the longest alternating even odd subarray
  18. Count of subarrays which start and end with the same element
  19. Count of subarrays having exactly K perfect square numbers
  20. Split array into two subarrays such that difference of their maximum is minimum
• Intermediate problems on Subarray:
  1. Print all K digit repeating numbers in a very large number
  2. Length of longest subarray whose sum is not divisible by integer K
  3. Min difference between maximum and minimum element in all Y size subarrays
  4. Longest subarray of non-empty cells after removal of at most a single empty cell
  5. First subarray with negative sum from the given Array
  6. Largest subarray with frequency of all elements same
  7. Bitwise operations on Subarrays of size K
  8. Count subarrays having sum of elements at even and odd positions equal
  9. Longest Subarray consisting of unique elements from an Array
  10. Minimum Decrements on Subarrays required to reduce all Array elements to zero
  11. Split array into two subarrays such that difference of their sum is minimum
  12. Maximize count of non-overlapping subarrays with sum K
  13. Smallest subarray which upon repetition gives the original array
  14. Split array into maximum subarrays such that every distinct element lies in a single subarray
  15. Maximize product of subarray sum with its minimum element
  16. Sum of products of all possible Subarrays
  17. Check if all subarrays contains at least one unique element
  18. Length of smallest subarray to be removed such that the remaining array is sorted
  19. Length of longest subarray having frequency of every element equal to K
  20. Length of the longest increasing subsequence which does not contain a given sequence as Subarray
• Hard Problems on Subarray:
  1. Length of smallest subarray to be removed to make sum of remaining elements divisible by K
  2. Maximum length of same indexed subarrays from two given arrays satisfying the given condition
  3. Count ways to split array into two equal sum subarrays by changing sign of any one array element
  4. Longest subarray in which all elements are smaller than K
  5. Maximize product of a strictly increasing or decreasing subarray
  6. Sum of maximum of all subarrays by adding even frequent maximum twice
  7. Longest subarray of an array which is a subsequence in another array
  8. Count of subarrays having product as a perfect cube
  9. Minimize difference between maximum and minimum array elements by removing a K-length subarray
  10. Maximum sum submatrix
  11. Minimum removal of elements from end of an array required to obtain sum K
  12. Check if any subarray of length M repeats at least K times consecutively or not
  13. Minimize flips on K-length subarrays required to make all array elements equal to 1
  14. Split array into K subarrays such that sum of maximum of all subarrays is maximized
  15. Find minimum subarray sum for each index i in subarray [i, N-1]
  16. Longest subarray with GCD greater than 1
  17. Longest subsegment of ‘1’s formed by changing at most k ‘0’s
  18. Lexicographically smallest Permutation of Array by reversing at most one Subarray
  19. Find a subsequence which upon reversing gives the maximum sum subarray
  20. Minimize steps to make Array elements 0 by reducing same A[i] – X from Subarray

Problems on Subsequence:

• Easy Problems on Subsequence:
  1. Longest subsequence having equal numbers of 0 and 1
  2. Powers of two and subsequences
  3. Longest Subsequence where index of next element is arr[arr[i] + i]
  4. Number of subsequences with zero sum
  5. Longest sub-sequence with maximum GCD
  6. Maximum Bitwise AND value of subsequence of length K
  7. Length of the longest subsequence such that xor of adjacent elements is non-decreasing
  8. Maximum product of bitonic subsequence of size 3
  9. Length of Smallest Subsequence such that sum of elements is greater than equal to K
  10. Longest subsequence of even numbers in an Array
  11. Maximum length Subsequence with alternating sign and maximum Sum
  12. Count of possible subarrays and subsequences using given length of Array
  13. Maximum bitwise OR value of subsequence of length K
  14. Count of subsequences consisting of the same element
  15. Smallest occurring element in each subsequence
  16. Length of the longest subsequence consisting of distinct elements
  17. Minimize elements to be added to a given array such that it contains another given array as its subsequence
  18. Maximize subsequences having array elements not exceeding length of the subsequence
  19. Length of longest subsequence consisting of distinct adjacent elements
  20. Maximum Sum Subsequence
• Intermediate Problems on Subsequence:
  1. Minimum removals required to make a given array Bitonic
  2. Check if a non-contiguous subsequence same as the given subarray exists or not
  3. Minimize the number of strictly increasing subsequences in an array
  4. Count of unique subsequences from given number which are power of 2
  5. Minimum number of insertions required such that first K natural numbers can be obtained as sum of a subsequence of the array
  6. Length of longest subsequence such that prefix sum at every element remains greater than zero
  7. Check if given Array can be divided into subsequences of K increasing consecutive integers
  8. Longest Subsequence such that difference between adjacent elements is either A or B
  9. Count subsequences of Array having single digit integer sum K
  10. Shortest Subsequence with sum exactly K
  11. Printing Longest Bitonic Subsequence
  12. Sorted subsequence of size 3 in linear time using constant space
  13. Count of subsequences having maximum distinct elements
  14. Construct array having X subsequences with maximum difference smaller than d
  15. Print all subsequences of a string using ArrayList
  16. Longest Subsequence with at least one common digit in every element
  17. Maximum Sum Subsequence of length k
  18. Sum of minimum element of all sub-sequences of a sorted array
  19. Find all combinations of two equal sum subsequences
  20. Minimum cost of choosing 3 increasing elements in an array of size N
• Hard Problems on Subsequence:
  1. Number of subsequences with positive product
  2. Longest subsequence having difference atmost K
  3. Find all subsequences with sum equals to K
  4. Maximize product of digit sum of consecutive pairs in a subsequence of length K
  5. Count of subsequences of length atmost K containing distinct prime elements
  6. Sum of all subsequences of length K
  7. Minimize sum of smallest elements from K subsequences of length L
  8. Unique subsequences of length K with given sum
  9. Smallest subsequence with sum of absolute difference of consecutive elements maximized
  10. Maximize product of same-indexed elements of same size subsequences
  11. Longest Increasing Subsequence having sum value atmost K
  12. Longest subsequence of a number having same left and right rotation
  13. Maximize length of Non-Decreasing Subsequence by reversing at most one Subarray
  14. Maximum subsequence sum possible by multiplying each element by its index
  15. Generate all distinct subsequences of array using backtracking
  16. Maximum subsequence sum such that no K elements are consecutive
  17. Print all possible K-length subsequences of first N natural numbers with sum N
  18. Longest subsequence having difference between the maximum and minimum element equal to K
  19. Maximize difference between sum of even and odd-indexed elements of a subsequence
  20. Convert an array into another by repeatedly removing the last element and placing it at any arbitrary index

Problems on Subset:

• Easy Problems on Subset:
  1. Find if there is any subset of size K with 0 sum in an array of -1 and +1
  2. Sum of sum of all subsets of a set formed by first N natural numbers
  3. Count of subsets not containing adjacent elements
  4. Sum of the sums of all possible subsets
  5. Find whether an array is subset of another array
  6. Total number of Subsets of size at most K
  7. Check if it is possible to split given Array into K odd-sum subsets
  8. Partition a set into two subsets such that difference between max of one and min of other is minimized
  9. Sum of all possible expressions of a numeric string possible by inserting addition operators
  10. Check if it’s possible to split the Array into strictly increasing subsets of size at least K
  11. Largest subset of Array having sum at least 0
• Intermediate Problems on Subset:
  1. Number of subsets with sum divisible by m
  2. Fibonacci sum of a subset with all elements <= k
  3. Number of possible Equivalence Relations on a finite set
  4. Largest divisible pairs subset
  5. Recursive program to print all subsets with given sum
  6. Subset Sum Queries in a Range using Bitset
  7. Find all distinct subset (or subsequence) sums of an array | Set-2
  8. Sum of (maximum element – minimum element) for all the subsets of an array
  9. Count no. of ordered subsets having a particular XOR value
  10. Sum of subsets of all the subsets of an array
  11. Perfect Sum Problem
  12. Count of subsets having sum of min and max element less than K
  13. Split array into two equal length subsets such that all repetitions of a number lies in a single subset
  14. Nth Subset of the Sequence consisting of powers of K in increasing order of their Sum
  15. Largest possible Subset from an Array such that no element is K times any other element in the Subset
  16. Check if an array can be split into subsets of K consecutive elements
• Hard Problems on Subset:
  1. Minimize count of divisions by D to obtain at least K equal array elements
  2. Split array into K-length subsets to minimize sum of second smallest element of each subset
  3. Median of all non-empty subset sums
  4. Minimum removals required such that sum of remaining array modulo M is X
  5. Sum of length of two smallest subsets possible from a given array with sum at least K
  6. Reduce sum of any subset of an array to 1 by multiplying all its elements by any value
  7. Sum of all subsets whose sum is a Perfect Number from a given array
  8. Minimize sum of incompatibilities of K equal-length subsets made up of unique elements
  9. Maximize sum of subsets from two arrays having no consecutive values
  10. Product of the maximums of all subsets of an array
  11. Count ways to place ‘+’ and ‘-‘ in front of array elements to obtain sum K
  12. Count ways to split array into two subsets having difference between their sum equal to K
  13. Find the subset of Array with given LCM
  14. Count of subsets whose product is multiple of unique primes
  15. Minimum count of elements to be inserted in Array to form all values in [1, K] using subset sum
  16. Maximum subset sum having difference between its maximum and minimum in range [L, R]
  17. Find all unique subsets of a given set using C++ STL
  18. Subset sum problem where Array sum is at most N

Data Structure and Algorithms Course
Recent articles on Subarray
Recent articles on Subsequence
Recent articles on Subset

Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above