Колькасць самых працяглых паслядоўнасцей


Узровень складанасці серада
Часта пытаюцца ў амазонка Samsung Zoho
масіў Дынамічнае праграмаванне

Пастаноўка праблемы

У задачы "Колькасць даўжэйшых паслядоўнасцей" гаворыцца, што вам дадзены масіў памерам n []. Надрукуйце колькасць найбольш працяглых паслядоўнасцей у ім.

Колькасць самых працяглых паслядоўнасцей

Прыклад

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

Тлумачэнне: На прыведзеным вышэй малюнку можна ўбачыць найбольш працяглыя паслядоўнасці.

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

выхад: 1 (1,2,3,4,5 - самая доўгая тут паслядоўнасць)

Алгарытм колькасці даўжэй павялічваюцца наступстваў

  1. Ініцыялізаваць масіў а [] з цэлае тып памеру 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 у масіве if 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

Аналіз складанасці

Складанасць часу

O (n * n) дзе n - колькасць элементаў у дадзеным масіве a []. Складанасць часу такая ж, як неабходная для таго, каб знайсці найбольш працяглую паслядоўнасць.

Касмічная складанасць

Аб (п) таму што мы выкарыстоўвалі дадатковае n месца. Мы выкарысталі масіў len [], які захоўвае самую працяглую паслядоўнасць, якая заканчваецца на i-ы элемент.