सबसे लंबे समय तक किसी परिणाम है कि पहले बढ़ जाती है तो कम हो जाती है

Question

मैं निम्नलिखित प्रश्न हल करने के लिए कोशिश कर रहा हूँ:

---

एक अनुक्रम जिसमें तत्वों पहले कमी के मूल्य में और फिर वृद्धि अनुक्रम कहा जाता है वी। वैध वी-अनुक्रम में घटती हुई कम से कम एक तत्व कम होने और कम से कम एक तत्व होना चाहिए।

उदाहरण के लिए, "5 3 1 9 17 23" एक मान्य वी-अनुक्रम है जिसमें कम से कम 5 और 3, और बढ़ती भुजा में 9 तत्व 17, 17 और 23 में दो तत्व हैं। लेकिन अनुक्रम "6 4 2" या "8 10 15" अनुक्रम में से कोई भी नहीं है क्योंकि "6 4 2" में बढ़ते हिस्से में कोई तत्व नहीं है जबकि "8 10 15" में घटते हिस्से में कोई तत्व नहीं है।

अनुक्रम से शून्य या अधिक तत्वों को हटाकर अनुक्रम का उप-अनुक्रम प्राप्त किया जाता है। उदाहरण के लिए परिभाषा "7", "2 10", "8 2 7 6", "8 2 7 10 6" आदि "8 2 7 10 6"

के अनुक्रमिक उप-अनुक्रम हैं एन संख्याओं के अनुक्रम को देखते हुए अपने सबसे लंबे उप अनुक्रम को खोजें जो एक वी-अनुक्रम है।

---

मैं वर्तमान में एक O (n^2) समाधान जिसमें मैं पहली बार एक सरणी (एम []) इस तरह के प्रारंभ है कि प्रत्येक मीटर [i] में 'i' सरणी के भीतर शुरूआती सबसे लंबे समय तक बढ़ती दृश्यों शामिल है।

इसी तरह, मैं एक और सरणी (डी []) शुरू करता हूं, जैसे कि प्रत्येक डी [i] उस बिंदु पर सबसे लंबे समय तक घटने वाला अनुक्रम होता है।

इन आपरेशनों के

दोनों O (n^2)

मैं अब इन सरणियों के माध्यम से जाने के लिए और मीटर की अधिकतम मूल्य चुनें ले [i] + d [i] -1, आवश्यक शर्तों संतुष्ट हैं ऐसा है कि।

मैं क्या जानना चाहता हूं - क्या कोई ओ (एन एलजी एन) समाधान है ?? क्योंकि मेरा समाधान आवश्यक समय सीमा के भीतर नहीं चलता है। आप :) धन्यवाद

कोड:

#include<cstdio> 
#include<algorithm> 

using namespace std; 



int m[ 200000 ]; 
int d[200000 ]; 
int n; 
int arr[200000 ]; 

void LIS() 
{ 
    m[ n-1 ] = 1; 

    int maxvPos = -1; 
    int maxv = -1; 

    for(int i=n-2; i>=0; i--) 
    { 
     maxv = -1; 
     for(int j=i+1; j<n; j++) 
     { 
      if((m[j]+1 > maxv) && (arr[i] < arr[j])) 
      { 
       maxv = m[j]+1; 
       maxvPos = j; 
      } 


     } 
     if(maxv>0) 
      { 
       m[i] = maxv; 
      } 

      else 
       m[i ] = 1; 
    } 

} 

void LDS() 
{ 
     d[0] = 1; 

    int maxv = -1; 
    int maxvPos = -1; 

    for(int i=1; i<n; i++) 
    { 
     maxv = -1; 
     for(int j=i-1; j>=0; j--) 
     { 
      if((d[j]+1 > maxv) && arr[j]>arr[i]) 
      { 
       maxv = d[j]+1; 
       maxvPos = j; 
      } 
     } 

     if(maxv>0) 
      d[i] = maxv; 

     else 
      d[i]=1; 
    } 

} 

int solve() 
{ 
    LIS(); 
    LDS(); 

    int maxv = 0; 
    int curr = 0; 

    for(int i=0; i<n; i++) 
    { 
     curr = d[i] + m[i] -1 ; 

     if((d[i]>0) && (m[i]>0)) 
     { 
      if(curr != 1) 
      maxv = max(curr, maxv); 
     } 

    } 

    return maxv; 

} 

/* static void printArr(int[] a) 
{ 
    for(int i : a) 
     System.out.print(i + " "); 

    System.out.println(); 
} */ 


int main() 
{ 
    scanf("%d", &n); 

    for(int i=0; i<n; i++) 
    { 
     scanf("%d", &arr[i]); 
    } 

    printf("%d\n", solve()); 
    return 0; 

} 

Answer 1

सबसे लंबे समय तक वृद्धिमान परिणाम समस्या के लिए O(NlgK) एल्गोरिथ्म, जहां K एलआईएस लंबाई है कर रहे हैं। आप एल्गोरिदम के विवरण के लिए Wikipedia देख सकते हैं। LightOJ में भी एक अच्छा ट्यूटोरियल है (इसे लॉगिन की आवश्यकता हो सकती है)।

Answer 2

संपादित करें: ओह, यह उत्तर गलत है। मैं लंबे अनुरूप अनुक्रम बनाने के लिए तत्वों को हटाने में सक्षम होने के बारे में हिस्सा याद किया। फिर भी, मनोरंजन के लिए, यहाँ सरल मामले में जहां आप तत्वों को हटाने के लिए नहीं मिलता है के लिए एक समाधान है:

मैं एक हे (एन) समाधान के बारे में सोच सकते हैं:

एक बार सूची चलो।

• सबसे लंबे समय तक v-अनुक्रम की शुरुआत देखा सबसे लंबे समय तक v-अनुक्रम देखा
• वर्तमान v-अनुक्रम
• वर्तमान स्कैन स्थिति
• वर्तमान स्कैन राज्य (आरोही की शुरुआत की
• लंबाई: कुछ चर बनाए रखें या अवरोही)

प्रारंभिक पॉइंटर्स को पहले तत्व के लिए प्रारंभ करें, शून्य से सबसे लंबा, और स्कैन स्थिति अवरोही करने के लिए प्रारंभ करें।

1. सूची तब तक चलें जब तक संख्याएं उतरती हैं और अवरोही स्थिति में।
2. जब कोई बढ़ती संख्या का सामना करना पड़ता है, तो आरोही स्थिति में बदलें और
3. पर चलते रहें जब अगला घटती संख्या encoutered हो, यह एक वी-अनुक्रम का अंत है।
4. वर्तमान में सबसे लंबे समय से सामना किए गए वी-अनुक्रम के साथ तुलना करें और अपडेट करें कि यदि यह लंबा है। उतरते
5. अगले अनुक्रम चलो
6. सरणी के अंत में, लौट सबसे लंबे समय तक अनुक्रम की शुरुआत और लंबाई के लिए वर्तमान v-अनुक्रम और राज्य स्कैन की शुरुआत
7. रीसेट।

Answer 3

यह एक ओ (एन) समाधान है। इसे मूल उदाहरणों पर जांच लिया गया।
मुझे बताएं कि क्या इसमें कोई समस्या है या यदि यह किसी विशेष मामले के लिए काम नहीं करता है।

कोड:

#include<stdio.h> 
int max(int a,int b) 
{ 
return (a >= b ? a : b); 
} 
int main() 
{ 
    int i,j,n; 
    scanf("%d",&n); 
    int A[200022]; 
    int dec[200022]={0}; 
    int V[200022]={0}; 
    int state[200022]={0}; 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",&A[i]); 
    } 
    if(A[0] > A[1]) 
     state[0]=1; 
    for(i=1;i<n;i++) 
    { 
     j=i-1; 
      if(A[i] < A[j]) 
      {  
       dec[i]=max(dec[i],dec[j]+1); 
       V[i]=max(V[i],V[j]); 
       state[i]=1; 
      }  
      else if(A[i] == A[j]) 
      {  
       dec[i]=dec[j]; 
       V[i]=V[j]; 
       state[i]=state[j]; 
      } 
      else 
      { 
       if(state[j]==1) 
       { 
        dec[i]=dec[i]; 
        V[i]=max(V[i],dec[j]+1); 
        V[i]=max(V[i],V[j]+1); 
        state[i]=1; 
       } 
       else 
       { 
        dec[i]=dec[i]; 
        V[i]=max(V[i],V[j]); 
       } 
      } 

// printf("%d %d\n",dec[i],V[i]); 
} 
    if(V[n-1] == 0) 
     printf("0\n"); 
    else 
     printf("%d\n",V[n-1]+1); 
} 

Answer 4

निर्माण सरणी इंक [i] जहां परिणाम को एक [i] के साथ समाप्त इंक [i] भंडार सबसे लंबे समय तक बढ़ाने से। सरणी dec का निर्माण [i] जहां dec [i] ए [i] के साथ समाप्त होने वाले सबसे लंबे समय तक घटते हुए स्टोर को स्टोर करता है।

तो की अधिकतम मान निकालने (इंक [i] + दिसं [मैं] - 1)