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


Сложный уровень средний
Часто спрашивают в Амазонка Samsung Zoho
массив Динамическое программирование

Постановка задачи

Задача «Число самой длинной возрастающей подпоследовательности» утверждает, что вам дан массив a [] размера n. Выведите в нем количество самых длинных возрастающих подпоследовательностей.

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

Пример

a[ ] = {1, 2, 5, 4, 7}
2

Объяснение: На изображении выше можно увидеть самые длинные возрастающие подпоследовательности.

Вход: a [] = {1, 2, 3, 4, 5}

Выход: 1 (1,2,3,4,5 - самая длинная подпоследовательность здесь)

Алгоритм определения количества самой длинной возрастающей подпоследовательности

  1. Инициализировать массив a [] из целое тип размера n.
  2. Создайте функцию, чтобы найти количество самые длинные возрастающие подпоследовательности которые принимают массив целочисленного типа и его размер в качестве параметров.
  3. Создайте два массива целочисленного типа len и cnt размера n и инициализируйте каждый элемент обоих массивов как 1. Также инициализируйте целочисленную переменную lis = 1.
  4. Пройдите от 1 до n-1, используя i, и создайте внутренний цикл от 0 до i-1.
  5. Проверьте, больше ли элемент в массиве a [] по текущему индексу внешнего цикла, чем элемент в массиве a [] по текущему индексу внутреннего цикла, проверьте, имеет ли значение + 1 в массиве len [] по текущему индексу внутреннего цикл больше, чем элемент в массиве len [] по текущему индексу внешнего цикла, обновить значение в массиве len [] по текущему индексу внешнего цикла как значение + 1 в массиве len [] по текущему индексу внутреннего цикла и значение в массиве cnt [] по текущему индексу внешнего цикла как значение в массиве cnt [] по текущему индексу внутреннего цикла.
  6. Иначе, если значение + 1 в массиве, если len [] в текущем индексе внутреннего цикла равно элементу в массиве len [] в текущем индексе внешнего цикла, обновить значение в массиве cnt [] в текущем индексе внешнего цикла как сумма значения в массиве cnt [] в текущем индексе внутреннего цикла и самого внешнего цикла.
  7. Сохраните максимум lis и len [i] в ​​lis.
  8. Инициализировать переменную ans как 0.
  9. Снова перейдите от 0 к n-1 и проверьте, равно ли len [i] lis, чтобы добавить значение по текущему индексу cnt в ans.
  10. Возврат анс.

Код:

Программа на C ++ для поиска номера самой длинной возрастающей подпоследовательности

#include <bits/stdc++.h>
using namespace std;

class Longestsubseq{
    public:
        int numOfIncSubseq(int a[], int n){
        
        int len[n], cnt[n]; 
        
        for(int i=0; i<n; i++){
            len[i]=1;
            cnt[i]=1;
        }
        
        int lis = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(a[i] > a[j]){
                
                    if(len[j]+1 > len[i]){
                        len[i] = len[j]+1;
                        cnt[i] = cnt[j];
                    }
                    
                    else if(len[j]+1 == len[i]){
                        cnt[i] += cnt[j];
                    }
                }
        
                lis = max(lis, len[i]);
            }
        }
        
        int ans = 0;
        
        for(int i=0; i<n; i++){
            if(len[i] == lis)ans += cnt[i];
        }
        
        return ans;
    }
};

int main(){
    Longestsubseq ls;
    
    int a[] = {1,2,5,4,7};
    int n = sizeof(a)/sizeof(a[0]);
    
    cout<<(ls.numOfIncSubseq(a, n));
    
    return 0;
}
2

Программа на Java для поиска номера самой длинной возрастающей подпоследовательности

import java.util.*;

class Longestsubseq{

    static int numOfIncSubseq(int[] a, int n){
    
        int[] len = new int[n];
        int[] cnt = new int[n]; 
        
        for(int i=0; i<n; i++){
            len[i]=1;
            cnt[i]=1;
        }
        
        int lis = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(a[i] > a[j]){
        
                    if(len[j]+1 > len[i]){
                        len[i] = len[j]+1;
                        cnt[i] = cnt[j];
                    }
        
                    else if(len[j]+1 == len[i]){
                        cnt[i] += cnt[j];
                    }
                }
        
                lis = Math.max(lis, len[i]);
            }
        }
        
        int ans = 0;
        
        for(int i=0; i<n; i++){
            if(len[i] == lis)ans += cnt[i];
        }
        
        return ans;
    }
    
    public static void main (String[] args){
        int[] a = {1,2,5,4,7};
        int n = a.length;
        
        System.out.println(numOfIncSubseq(a, n));
    }
}
2

Анализ сложности

Сложность времени

О (п * п) где n - количество элементов в данном массиве a []. Сложность по времени такая же, как и для поиска самой длинной возрастающей подпоследовательности.

Космическая сложность

О (п) потому что мы использовали дополнительное пространство n. Мы использовали массив len [], который хранит самую длинную возрастающую подпоследовательность, заканчивающуюся i-м элементом.