अधिकतम कुल - एल्गोरिदम के साथ सबस्ट्रिंग की गणना करने के लिए अलगो अनुकूलित करें

"एन" संख्याओं की निम्नलिखित श्रृंखला से अधिकतम कुल उप-अनुक्रम प्राप्त करने के लिए ऑप्टिमाइज़/स्मार्ट एल्गो क्या होगा उदाहरण:

Input:             Index   0  1  2  3  4  5  6  7
Series -1  0  3 -2  5 -2  6  1

trials  :          start :4 end :7 total :10
start :6 end :7 total :7


Output (Max Total Sub-sequence):  start :2  ,end:7 , total:11

उत्तर:

आप एक O(n) एल्गोरिथम को आसानी से लागू कर सकते हैं; मैं दो तरीकों के बारे में सोच सकता हूं:

1) डीपी:

चलो dp[i] तत्व i पर समाप्त होने वाले अधिकतम अनुक्रम की लंबाई हो dp[0] = element[0]. और मैं प्रत्येक के लिए, dp[i] = max( dp[i - 1] + element[i], element[i] ). ऐसा इसलिए है क्योंकि आपके पास दो विकल्प हैं, या तोवर्तमान तत्व को पिछले अधिकतम अनुक्रम में जोड़ना, या एक नया बनाना। सभी i's पर अधिकतम लें, और वह आपका उत्तर है। आप परिवर्तनों को आसानी से ट्रैक करके शुरुआत और अंत पा सकते हैं।

2) एक सरल सहज ज्ञान युक्त एल्गोरिथ्म:

सबसे पहले, उपसर्ग योग सरणी बनाएं, ताकि उपसर्ग [i] तत्वों का योग हो 0...i. अब यदि आपके पास a से b तक का क्रम है, तो इसका योग स्पष्ट रूप से है prefix[b] - prefix[a - 1] (ए = 0 एक विशेष मामला है जिसे संभाला जा सकता हैसरलता )। अब मान लीजिए कि हमने बी तय कर दिया है, तो इष्टतम विकल्प को उपसर्ग [ए -1] को कम करना चाहिए। इसलिए हम अब तक न्यूनतम उपसर्ग [j] रखते हुए, सभी i"s पर पुनरावृति कर सकते हैं। उत्तर प्रत्येक चरण पर सभी चरणों में अधिकतम है: prefix[i] - prefix[j].

यहाँ स्यूडोकोड है:

// Compute prefix sum array easily and trivially ( ask me if you want how )

int curMin = 0, answer = - INFINITY;

for i = 0 to n - 1

answer = max( answer, prefix[i] - curMin );

curMin = min( curMin, prefix[i] );

एक रैखिक एल्गोरिथ्म मौजूद है। उदाहरण के लिए इसे देखें http://wordaligned.org/articles/the-maximum-subsequence-problem