एक सरणी

Question

में सबसे बड़ी तत्वों के साथ अनुवर्ती खोजें, मैंने हाल ही में एक कंपनी के साथ साक्षात्कार किया और उन्होंने मुझे एक एल्गोरिदम लिखने के लिए कहा जो बाद में किसी सरणी में तत्वों के साथ मिलती है। सरणी में तत्व नकारात्मक हो सकते हैं। क्या इसके लिए ओ (एन) समाधान है? किसी भी अच्छे समाधान की बहुत सराहना की जाती है।

Answer 1

आप अनुक्रमिक संख्या में से सबसे बड़ी राशि चाहते हैं तो कुछ इस तरह काम कर सकते हैं:

$cur = $max = 0; 
foreach ($seq as $n) 
{ 
    $cur += $n; 
    if ($cur < 0) $cur = 0; 
    if ($cur > $max) $max = $cur; 
} 

कि सिर्फ मेरे सिर के ऊपर से है, लेकिन यह सही लगता है। (उपेक्षा कर यह मानता है कि 0 खाली और सभी नकारात्मक सेट के लिए जवाब है।)

संपादित करें:

आप भी अनुक्रम स्थिति चाहते हैं:

$cur = $max = 0; 
$cur_i = $max_i = 0; 
$max_j = 1; 

foreach ($seq as $i => $n) 
{ 
    $cur += $n; 
    if ($cur > $max) 
    { 
    $max = $cur; 
    if ($cur_i != $max_i) 
    { 
     $max_i = $cur_i; 
     $max_j = $max_i + 1; 
    } 
    else 
    { 
     $max_j = $i + 1; 
    } 
    } 

    if ($cur < 0) 
    { 
    $cur = 0; 
    $cur_i = $i + 1; 
    } 
} 

var_dump(array_slice($seq, $max_i, $max_j - $max_i), $max); 

के लिए एक अधिक संक्षिप्त तरीके से हो सकती है कर दो। फिर, यह वही मान्यताओं (कम से कम एक सकारात्मक पूर्णांक) है। इसके अलावा, यह केवल पहला सबसे बड़ा अनुक्रम पाता है।

संपादित करें: इसे max_len के बजाय max_j (अनन्य) का उपयोग करने के लिए बदलें।

Answer 2

मुझे लगता है कि आप सबसे लंबे समय तक बढ़ने के बाद मानते हैं।

इसके लिए O(n) समाधान नहीं है।

डुप्लिकेट सरणी बनाने के लिए एक बहुत ही बेवकूफ समाधान होगा, इसे O(NlogN) में सॉर्ट करें और फिर क्रमबद्ध सरणी और मूल सरणी के LCS को O(N^2) ले लें।

LCS के समान प्रत्यक्ष डीपी आधारित समाधान भी है जो O(N^2) भी लेता है, जिसे आप here देख सकते हैं।

लेकिन यदि आप सबसे लंबे समय तक बढ़ते क्रम (लगातार) का मतलब रखते हैं। यह O(N) में किया जा सकता है।

Answer 3

यदि आप सबसे लंबे समय तक बढ़ने का मतलब रखते हैं, तो कोडाडिक्ट का उत्तर देखें।

दूसरी ओर आप अधिकतम राशि साथ उप सरणी खोजने मतलब है (केवल नकारात्मक मूल्यों के साथ समझ में आता है), तो वहाँ एक सुंदर, गतिशील प्रोग्रामिंग शैली रैखिक समय समाधान है:

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Answer 4

सी समारोह इस तरह दिखता है:

int largest(int arr[], int length) 
{ 
    int sum= arr[0]; 
    int tempsum=0; 
    for(int i=0;i<length;i++){ 
    tempsum+=arr[i]; 
    if(tempsum>sum) 
     sum=tempsum; 
    if(tempsum<0) 
     tempsum=0; 
    } 
    return sum; 
} 

Answer 5

निम्नलिखित कोड का प्रयास करें:

#include <stdio.h> 

int main(void) { 
    int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3}; 
    int cur = arr[0] >= 0? arr[0] : 0, max = arr[0]; 
    int start = 0, end = 0; 
    int i,j = cur == 0 ? 1 : 0; 
    printf("Cur\tMax\tStart\tEnd\n"); 
    printf("%d\t%d\t%d\t%d\n",cur,max,start,end); 
    for (i = 1; i < 10; i++) { 
     cur += arr[i]; 
     if (cur > max) { 
      max = cur; 
      end = i; 
      if (j > start) start = j; 
     }  
     if (cur < 0) { 
      cur = 0; 
      j = i+1; 
     } 
     printf("%d\t%d\t%d\t%d\n",cur,max,start,end); 
    } 
    getchar(); 
} 

Answer 6

void longsub(int a[], int len) { 

     int localsum = INT_MIN; 
     int globalsum = INT_MIN; 
     int startindex = 0,i=0; 
     int stopindex = 0; 
     int localstart = 0; 

     for (i=0; i < len; i++) { 
       if (localsum + a[i] < a[i]) { 
         localsum = a[i]; 
         localstart = i; 
       } 
       else { 
         localsum += a[i]; 
       } 

       if (localsum > globalsum) { 
         startindex = localstart; 
         globalsum = localsum; 
         stopindex = i; 
       } 

     } 

     printf ("The begin and end indices are %d -> %d (%d).\n",startindex, stopindex, globalsum); 

} 

Answer 7

यह समस्या दो अलग अलग तरीकों से हल किया जा सकता है।

पहले दृष्टिकोण में sum और MaxSum नामक दो चर हैं।

1. हम योग के मानों को जोड़ने पर रखेंगे और MaxSum साथ तुलना करेंगे, यदि राशि के लिए मूल्य MaxSum से अधिक है - MaxSum

2. को योग मान असाइन जाएगा दौरान योग के लिए मूल्य 0 से नीचे चला जाता है, हम योग को रीसेट कर देंगे और अगली इंडेक्स ऑन-वार्ड से नई संख्या जोड़ना शुरू कर देंगे। ऊपर समाधान के लिए नमूना कोड नीचे के रूप में प्रदान की जाती है:

   private static void FindMaxSum(int[] array) 
   { 
       int sum = 0; 
       int MaxSum = 0; 
   
       for (int i = 0; i < array.Length; i++) 
       { 
        sum += array[i]; 
   
        if (sum > MaxSum) 
        { 
         MaxSum = sum; 
        } 
        else if (sum < 0) 
        { 
         sum = 0; 
        } 
       } 
       Console.WriteLine("Maximum sum is: " + MaxSum); 
   } 
   

इस समस्या को हल करने के लिए दूसरा दृष्टिकोण है कि हम प्रत्येक और एक सरणी में प्रत्येक तत्व के माध्यम से जाना जाएगा। हमारे पास योग और मैक्ससम के समान 2 चर होंगे।

1. सबसे पहले हम अगले सरणी तत्व और योग के साथ योग के अतिरिक्त की तुलना करेंगे। कौन अधिक बड़ा है - वह मान योग चर में संग्रहीत किया जाएगा।

2. अगला हम योग और मैक्ससम के मूल्यों की तुलना करेंगे और जिनके पास अधिक मूल्य है - हम उस मान को मैक्ससम चर में सहेज लेंगे। नीचे वर्णित के रूप में नमूना कोड है:

   private static void FindMaxSum(int[] array) 
   { 
       int sum = array[0], Maxsum = array[0]; 
   
       for (int i = 1; i < array.Length; i++) 
       { 
        sum = Max(sum + array[i], array[i]); 
        Maxsum = Max(sum, Maxsum);    
       } 
   
       Console.WriteLine("Maximum sum is: " + Maxsum); 
   } 
   
   private static int Max(int a, int b) 
   { 
       return a > b ? a : b; 
   } 
   

Answer 8

आप एक सन्निहित परिणाम को जिसके लिए राशि अधिकतम है, मैं 4 algos अब तक पाया है क्या पूछ रहे हैं, तो: -

1. ब्रूट-फोर्स: नेस्टेड लूप का उपयोग करके सभी संभावित रकम खोजें और maxSum को अपडेट करना जारी रखें यदि आपको maxSum के पिछले सेट मान से अधिक राशि मिलती है। समय जटिलता हे है (एन^2)

2. गतिशील प्रोग्रामिंग समाधान: यह एक उल्लेखनीय सुरुचिपूर्ण समाधान जो मैं StackOverflow पर ही पाया जाता है - https://stackoverflow.com/a/8649869/2461567v - समय जटिलता: हे (एन), अंतरिक्ष जटिलता: O (n)

3. स्मृति के बिना डी पी - Kadane एल्गोरिथ्म - https://en.wikipedia.org/wiki/Maximum_subarray_problem - समय जटिलता: हे (एन), अंतरिक्ष जटिलता: हे (1)

4. फूट डालो और राज समाधान - http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf समय जटिलता: हे (nlgn)