algorithm
सबसे लंबे समय तक बढ़ते परिणाम

सबसे लंबे समय तक बढ़ती मूल जानकारी

सबसे लंबे समय तक बढ़ने वाली उपसर्ग समस्या को इनपुट इनपुट अनुक्रम से प्राप्त करना है जिसमें बाद के तत्वों को उच्चतम से निम्नतम क्रम में क्रमबद्ध किया जाता है। सभी परवर्ती सन्निहित या अद्वितीय नहीं हैं।

लंबे समय तक बढ़ती प्रक्रिया के आवेदन:

एल्गोरिथ्म जैसे लॉन्गेस्ट इनकमिंग सबड्रेन्स, लॉन्गेस्ट कॉमन सबअर्सेन्स का उपयोग वर्जन कंट्रोल सिस्टम जैसे गिट और आदि में किया जाता है।

एल्गोरिथम का सरल रूप:

1. ऐसी अद्वितीय रेखाएँ खोजें जो दोनों दस्तावेज़ों के लिए सामान्य हों।
2. पहले दस्तावेज़ से ऐसी सभी लाइनें लें और दूसरे दस्तावेज़ में उनकी उपस्थिति के अनुसार उन्हें ऑर्डर करें।
3. परिणामी अनुक्रम के LIS की गणना करें ( धैर्य क्रमबद्ध करके ), लाइनों का सबसे लंबा मिलान क्रम, दो दस्तावेजों की पंक्तियों के बीच एक पत्राचार।
4. पहले से मिलान किए गए लोगों के बीच प्रत्येक श्रेणी की रेखाओं पर एल्गोरिथ्म को पुनर्जीवित करें।

अब हम LCS समस्या का एक सरल उदाहरण मानते हैं। यहां, इनपुट अलग-अलग पूर्णांक a1,a2,...,an. का केवल एक अनुक्रम है a1,a2,...,an. , और हम इसमें सबसे लंबे समय तक बढ़ते हुए परिणाम खोजना चाहते हैं। उदाहरण के लिए, यदि इनपुट 7,3,8,4,2,6 है, तो सबसे लंबे समय तक बढ़ने वाला परिणाम 3,4,6 है ।

सबसे आसान तरीका इनपुट तत्वों को बढ़ते क्रम में सॉर्ट करना है, और LCS एल्गोरिदम को मूल और क्रमबद्ध अनुक्रमों पर लागू करना है। हालाँकि, यदि आप परिणामी सरणी को देखते हैं, तो आप देखेंगे कि कई मान समान हैं, और सरणी बहुत दोहरावदार दिखती है। यह सुझाव देता है कि एलआईएस (सबसे लंबे समय तक बढ़ती हुई) समस्या को केवल एक आयामी सरणी का उपयोग करके गतिशील प्रोग्रामिंग एल्गोरिदम के साथ किया जा सकता है।

छद्म कोड:

1. उन मूल्यों की एक सरणी का वर्णन करें जिन्हें हम गणना करना चाहते हैं।
   1 <= i <= n , ए (i) इनपुट के सबसे लंबे समय तक बढ़ते अनुक्रम की लंबाई हो। ध्यान दें कि हम जिस लंबाई में रुचि रखते हैं, वह max{A(i)|1 ≤ i ≤ n} ।
2. पुनरावृत्ति दें।
   1 <= i <= n , A(i) = 1 + max{A(j)|1 ≤ j < i और input(j) < input(i)}.
3. A के मानों की गणना करें।
4. इष्टतम समाधान खोजें।

एक इष्टतम समाधान की गणना करने के लिए निम्न प्रोग्राम ए का उपयोग करता है। पहला भाग एक मूल्य m की गणना करता है जैसे कि A (m) इनपुट के एक इष्टतम बढ़ते बाद की लंबाई है। दूसरा भाग एक इष्टतम बढ़ती हुई गणना की गणना करता है, लेकिन सुविधा के लिए हम इसे रिवर्स ऑर्डर में प्रिंट करते हैं। यह कार्यक्रम समय O (n) में चलता है, इसलिए संपूर्ण एल्गोरिथ्म O (n ^ 2) में चलता है।

भाग 1:

m ← 1 
for i : 2..n 
    if A(i) > A(m) then 
        m ← i 
    end if 
end for

भाग 2:

put a
while A(m) > 1 do 
    i ← m−1 
    while not(ai < am and A(i) = A(m)−1) do 
        i ← i−1 
    end while 
    m ← i 
    put a
 end while

पुनरावर्ती समाधान:

दृष्टिकोण 1:

LIS(A[1..n]):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)])
    B is subsequence of A[1..(n − 1)] with only elements less than a[n]
    (* let h be size of B, h ≤ n-1 *)
    m = max(m, 1 + LIS(B[1..h]))
    Output m

दृष्टिकोण 1: O(n*2^n) में समय की जटिलता

दृष्टिकोण 2:

LIS(A[1..n], x):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)], x)
    if (A[n] < x) then
        m = max(m, 1 + LIS(A[1..(n − 1)], A[n]))
    Output m

MAIN(A[1..n]):
    return LIS(A[1..n], ∞)

दृष्टिकोण 2 में समय जटिलता: O(n^2)

दृष्टिकोण 3:

LIS(A[1..n]):
    if (n = 0) return 0
    m = 1
    for i = 1 to n − 1 do
        if (A[i] < A[n]) then
            m = max(m, 1 + LIS(A[1..i]))
    return m

MAIN(A[1..n]):
    return LIS(A[1..i])

दृष्टिकोण 3 में समय जटिलता: O(n^2)

Iterative एल्गोरिथम:

फैशन में नीचे से पुनरावृत्त मूल्यों की गणना करता है।

LIS(A[1..n]):
    Array L[1..n]
    (* L[i] = value of LIS ending(A[1..i]) *)
    for i = 1 to n do
        L[i] = 1
        for j = 1 to i − 1 do
            if (A[j] < A[i]) do
                L[i] = max(L[i], 1 + L[j])
    return L

MAIN(A[1..n]):
    L = LIS(A[1..n])
        return the maximum value in L

Iterative दृष्टिकोण में समय की जटिलता: O(n^2)

सहायक स्थान: O(n)

इनपुट के रूप में {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} को लें। तो, दिए गए इनपुट के लिए सबसे लंबे समय तक बढ़ते परिणाम {0, 2, 6, 9, 11, 15} है ।

C # कार्यान्वयन

public class LongestIncreasingSubsequence
{
    private static int Lis(int[] input, int n)
    {
        int[] lis = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++)
        {
            lis[i] = 1;
        }
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (input[i] > input[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (max < lis[i])
                max = lis[i];
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return Lis(input, n);
    }
}