algorithm
अधिकतम सबअरे एल्गोरिदम

अधिकतम सबअरे एल्गोरिथ्म बुनियादी जानकारी

अधिकतम सबअरे की समस्या संख्या के एक-आयामी सरणी के भीतर सन्निहित सब्रे को खोजने की विधि है जिसमें सबसे बड़ा योग है।

समस्या को मूल रूप से 1977 में ब्राउन यूनिवर्सिटी के उल्फ ग्रेन्डर द्वारा प्रस्तावित किया गया था, डिजिटाइज्ड चित्रों में पैटर्न की अधिकतम संभावना अनुमान के लिए एक सरलीकृत मॉडल के रूप में।

हम इस तरह की समस्या कर सकते हैं, आइए हम विभिन्न पूर्णांकों की सूची पर विचार करें। हमें इसमें दिलचस्पी हो सकती है जिसमें पूरी तरह से आसन्न सबसे बड़ी राशि होगी। उदाहरण के लिए, यदि हमारे पास 5 राशि के साथ [3, 2] सरणी [0, 1, 2, -2, 3, 2] , तो अधिकतम उपश्रेणी [3, 2] ।

समाधान के लिए जानवर-बल दृष्टिकोण:

समाधान खोजने के लिए यह विधि सबसे अक्षम है। इसमें, हम हर एक संभावित सबरे के माध्यम से जा रहे हैं, और फिर उन सभी का योग ढूंढेंगे। अंत में, सभी मूल्यों की तुलना करें और अधिकतम सब्रे का पता लगाएं।

जानवर-बल दृष्टिकोण के लिए छद्म कोड:

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

Brute-Force विधि के लिए समय की जटिलता O(n^2) । तो आइए दृष्टिकोण को विभाजित करने और जीतने के लिए आगे बढ़ें।

विभाजित और समाधान के लिए जीतना:

बाईं ओर के सबरेज़ का योग, दाईं ओर के सबरेज़ का पता लगाएं। फिर, उन सभी के माध्यम से एक नज़र डालें जो केंद्र को विभाजित करते हैं, और अंत में अधिकतम राशि वापस करते हैं। क्योंकि यह एक विभाजित और एल्गोरिथ्म को जीतता है, हमें दो अलग-अलग कार्य करने की आवश्यकता है।

पहला कदम विभाजित है,

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

दूसरे भाग में, पहले भाग में बनाए गए अलग भाग को अलग करें।

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

डिवाइड और कॉन्कर विधि के लिए समय की जटिलता O(nlogn) । तो आइए गतिशील प्रोग्रामिंग दृष्टिकोण पर जाएं।

गतिशील प्रोग्रामिंग दृष्टिकोण:

इस समाधान को कडाने के एल्गोरिथ्म के रूप में भी जाना जाता है। यह रैखिक समय एल्गोरिथ्म है। यह समाधान 70 के दशक के उत्तरार्ध में जोसेफ बी। कडाने द्वारा दिया गया है।

यह एल्गोरिथ्म सिर्फ लूप से गुजरता है, लगातार वर्तमान अधिकतम राशि को बदल रहा है। दिलचस्प रूप से पर्याप्त है, यह एक गतिशील प्रोग्रामिंग एल्गोरिथ्म का एक बहुत ही सरल उदाहरण है, क्योंकि यह एक अतिव्यापी समस्या लेता है और इसे कम करता है इसलिए हम एक अधिक कुशल समाधान पा सकते हैं।

कोडेन के एल्गोरिथ्म का छद्म कोड:

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

कडाने के एल्गोरिथ्म के लिए समय जटिलता O(n) ।

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

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

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