अधिकतम उत्पाद अनुक्रम

Question

मुझे n पूर्णांक के अनुक्रम में बाद के अधिकतम उत्पाद को खोजने की आवश्यकता है। मैं एक एल्गोरिदम की तलाश में हूं, जरूरी नहीं कि कोड के रूप में व्यक्त किया जाए।

उदाहरण:

1. में: 3,1, -2,4। आउट: 4.
2. इन: 2,5, -1, -2, -4। आउट: 20. (2 * 5 * -1 * -2)।

मैंने O(n²) में एक एल्गोरिदम किया है, लेकिन अब मुझे O(n) में एक की आवश्यकता है।
मुझे पता है कि यह संभव है।

यह O(n) में कैसे किया जा सकता है?

Answer 1

यदि आपका सभी इनपुट> 0 था, तो अधिकतम उत्पाद सभी संख्याओं को एक साथ गुणा करके मिलेगा।

यदि आपका सभी इनपुट गैर-0 था और नकारात्मक संख्याओं की भी गिनती थी, तो फिर से अधिकतम संख्या सभी संख्याओं को एक साथ गुणा करके मिल जाएगी।

तो यह काम शून्य और नकारात्मक संख्याओं से निपटने में है।

आपको चलने वाले उत्पाद की गणना करने के बाद, आपको एक बार सूची में जाना होगा। यदि आप 0 तक पहुंचते हैं, तो उसके पहले सब कुछ एक उम्मीदवार सबसेट है और इसके विवरण (प्रारंभ सूचकांक, अंत सूचकांक, उत्पाद) को सहेजने की आवश्यकता है, यह अब तक के सबसे अच्छे से बेहतर होना चाहिए। अब एक नया चल रहा उत्पाद शुरू करें। यदि आप ऋणात्मक संख्या तक पहुंचते हैं, तो वह आइटम आपके चल रहे कुल में एक सशर्त ब्रेक है। नकारात्मक संख्या का उपयोग किये बिना चल रहे उत्पाद का मूल्यांकन आपके सर्वश्रेष्ठ के लिए किया जाएगा। लेकिन अब आपको 2 चलने वाले उत्पादों की आवश्यकता है, एक नकारात्मक संख्या वाला और एक नया। इस प्रकार बाद के गुणों को 2 सूचियों के खिलाफ काम करने की आवश्यकता है। इस बिंदु पर मेरे पास 2 चलने वाले उत्पाद होंगे। यदि आप एक और नकारात्मक संख्या हिट करते हैं, तो आपकी प्रत्येक चलती सूची को पहले वर्णित अनुसार विभाजित करने की आवश्यकता है। तो यदि आप छेड़छाड़ नहीं करते हैं तो आप बहुत सारी चल रही सूचियों के साथ समाप्त हो सकते हैं। मुझे लगता है कि आप रनिंग सूचियों को केवल 3 का ट्रैक रखने के लिए छीन सकते हैं: उपन्यास जो अभी शुरू हुआ है, नकारात्मक संख्याओं की अजीब गिनती के साथ निरंतर सूची और नकारात्मक संख्याओं की एक अजीब गिनती भी है। किसी भी उम्मीदवार उप-सूची चल रहे गुणा का हिस्सा नहीं है, यह देखने के लिए मूल्यांकन किया जाना चाहिए कि इसे छोड़ने से पहले यह सबसे अच्छा है।

अंत इसकी हे (एन)

Answer 2

गैर शून्य संख्या का एक रन की अधिकतम परिणाम को उत्पाद या तो सभी नंबरों का उत्पाद है (वहाँ नकारात्मक संख्या सम संख्या है), या यह है पर पहले ऋणात्मक संख्या के बाद सभी संख्याओं के उत्पाद से अधिक, और अंतिम संख्या तक सभी संख्याओं का उत्पाद।

यह आपको एक ओ (एन) समाधान देता है: अनुक्रम को गैर-शून्य संख्याओं के रनों में तोड़ें और नियम को प्रत्येक के पहले पैराग्राफ में लागू करें। इनमें से अधिकतम उठाओ।

सी की तरह इस के लिए अजगर कोड:

def prod(seq, a, b): 
    r = 1 
    for i in xrange(a, b): 
     r *= seq[i] 
    return r 

def maxprodnon0(seq, a, b): 
    firstneg = -1 
    negs = 0 
    for i in xrange(a, b): 
     if seq[i] >= 0: continue 
     negs += 1 
     if firstneg < 0: 
      firstneg = i 
     lastneg = i 
    if negs % 2 == 0: return prod(seq, a, b) 
    return max(prod(seq, firstneg + 1, b), prod(seq, a, lastneg)) 

def maxprod(seq): 
    best = 0 
    N = len(seq) 
    i = 0 
    while i < N: 
     while i < N and seq[i] == 0: 
      i += 1 
     j = i 
     while j < N and seq[j] != 0: 
      j += 1 
     best = max(best, maxprodnon0(seq, i, j)) 
     i = j 
    return best 

for case in [2,5,-1,-2,-4], [1,2,0,-4,5,6,0,7,1], [1,2,0,-4,5,6,-1,-1,0,7,1]: 
    print maxprod(case)