Maximum Product Subarray



  • hi,

    ich habe eine kleine coding uebung welche ich in c++ loese:

    Maximum Product Subarray
    Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be used.

    Examples:

    Input: arr[] = {6, -3, -10, 0, 2}
    Output: 180 // The subarray is {6, -3, -10}

    Input: arr[] = {-1, -3, -10, 0, 60}
    Output: 60 // The subarray is {60}

    Input: arr[] = {-2, -3, 0, -2, -40}
    Output: 80 // The subarray is {-2, -40}

    mich wuerde interessieren, wie ihr das loesen wuerdet? wenn moeglich in O(n) time...

    ich habs schon implementiert und poste danach meine loesung...



  • Ich würde zuerst ans http://en.wikipedia.org/wiki/Maximum_subarray_problem denken und statt a[i] immer log(a[i]) in den algo stopfen.
    edit: Vielleicht hat der Aufgabensteller genau deswegen 0 im Array ausgeschlossen?
    edit2: ach, Mist, Minuszahlen klappen ja auch nicht. Blöder log.



  • warum log(a[i]), hast du vor alle teil produkte zu speichern?



  • ArnoldSchw schrieb:

    warum log(a[i]), hast du vor alle teil produkte zu speichern?

    Wären es nur positive Zahlen und sagen wie mal log10, dann würde aus
    {1,100,1000,10,100}
    eben
    {0,2,3,1,2}
    und aus * würde +

    Dann könnte ich irgendeinen Algo für Maximal Sum Subarray abschreiben und wäre fertig.



  • Da alles Integer sind, kann man einfach greedy so viele nehmen, wie man will, solange keine 0 dabei ist. Nur auf das Vorzeichen muss man aufpassen:

    template <typename Iter, typename T = typename std::iterator_traits<Iter>::value_type>
    T mapros(Iter first, Iter last) {
      T max[3] = {0, 0, 0};
      for (; first != last; ++first) {
        if (!*first) {
          std::fill(max, max+2, 0);
        } else {
          std::for_each(max, max+2, [&](auto& x){x*=*first;});
          if (!max[0]) max[0] = *first;
          if (!max[1] && (max[0]<0)!=(*first<0)) max[1] = *first;
          max[2] = *std::max_element(max, max+3);
        }
      }
      return max[2];
    }
    


  • Bei Zeile 10 noch ein "else" hinzudenken.



  • Hier mal mein Versuch 😃
    Laufzeit O(n), Speicher O(1):

    #include <iostream>
    #include <vector>
    
    template <typename ForwardIterator>
    auto max_subarray_product(ForwardIterator start, ForwardIterator end) -> typename std::remove_reference<decltype(*start)>::type
    {
    	using Integer = decltype(max_subarray_product(start, end));
    
    	Integer value = 1, max_value = *start;
    	while (start != end)
    	{
    		value *= *start++;
    		if (start == end)
    		{
    			return std::max(value, max_value);
    		}
    		else if (!*start)
    		{
    			++start;
    			if (value > max_value)
    			{
    				max_value = value;
    			}
    			value = 1;
    		}
    	}
    	return max_value;
    }
    
    int main()
    {
    	std::vector<int> v1 = { 6, -3, -10, 0, 2 };
    	std::vector<int> v2 = { -1, -3, -10, 0, 60 };
    	std::vector<int> v3 = { -2, -3, 0, -2, -40 };
    
    	std::cout << max_subarray_product(v1.begin(), v1.end()) << '\n'; // 180
    	std::cout << max_subarray_product(v2.begin(), v2.end()) << '\n'; // 60
    	std::cout << max_subarray_product(v3.begin(), v3.end()) << '\n'; // 80
    }
    


  • happystudent schrieb:

    Hier mal mein Versuch 😃

    Probier mal mit

    std::vector<int> v4 = { -2, -2, -3 };
    

    , Ausgabe sollte 6 sein.

    Mein Code von oben stimmt doch, das else ist nicht nötig.



  • @happystudent:

    hier gibt dein algo -2 aus!?

    std::vector<int> v4 = { -2, -3, -1, -2, -40 };
    


  • mein algo (ich gebe start und endindex zurueck), bitte feedback:

    #include <iostream>
    #include <vector>
    #include <string>
    #include <numeric>
    #include <limits>
    
    auto find_max_product_subarray(std::vector<int> &vec) {
    	int start = 0;
    	int start_tmp = 0;
    	int end = 0;
    	int currProd = 0;
    	int maxProd = std::numeric_limits<int>::min();
    
    	for (int i = 0; i < vec.size(); i++) {
    		currProd *= vec[i];
    
    		if (currProd == 0) {
    			currProd = 1;
    			start_tmp = i+1;
    		}
    		else if (currProd > maxProd) {
    			maxProd = currProd;
    			start = start_tmp;
    			end = i;
    		}
    	}
    
    	return std::make_pair(start, end);
    }
    
    int main() {
      std::vector<int> ivec = {1, 2, 3, 4, -1, 0, 2, -2, 44, 8, -2, 0, 1, -550};
    
      auto p = find_max_product_subarray(ivec);
    
      std::cout << "start: " << p.first << ", end: " << p.second << std::endl;
    
      return 0;
    }
    


  • ArnoldSchw schrieb:

    bitte feedback:

    Ist falsch, oder?

    Gibt bei beiden Eingaben das falsche Resultat aus:

    {2,1}
    {1,0,-2,-2,-3}
    


  • @mapros: dein algo sieht gut aus...

    happystudent's algo hat auch ein problem hier...



  • @mapros: kannst du erklaeren wie dein algo funzt?



  • Oh, dann habe ich die Aufgabenstellung falsch verstanden, dachte dass die Bereiche immer durch eine 0 abgetrennt sind ^^



  • @mapos habe meinen algo gefixt:

    #include <iostream> 
    #include <vector> 
    #include <string> 
    #include <numeric> 
    #include <limits> 
    
    auto find_max_product_subarray(std::vector<int> &vec) { 
        int start = 0; 
        int start_tmp = 0; 
        int end = 0; 
        int currProd = 0; 
        int maxProd = std::numeric_limits<int>::min();
    
        for (int i = 0; i < vec.size(); i++) { 
            currProd *= vec[i]; 
    
            if (currProd == 0) { 
                currProd = 1; 
                start_tmp = i+1; 
            } 
            else if (currProd > maxProd) { 
                maxProd = currProd; 
                start = start_tmp; 
                end = i; 
            } 
        } 
    
        currProd = 1;
        start_tmp = vec.size() - 1;
    
        for (int i = vec.size() - 1; i >= 0; i--) { 
            currProd *= vec[i]; 
    
            if (currProd == 0) { 
                currProd = 1; 
                start_tmp = i-1; 
            } 
            else if (currProd > maxProd) { 
                maxProd = currProd; 
                start = start_tmp; 
                end = i; 
            } 
        }
    
        return std::make_pair(start, end); 
    } 
    
    int main() { 
      std::vector<int> ivec1 = {2,1}; 
      auto p1 = find_max_product_subarray(ivec1); 
      std::cout << "start: " << p1.first << ", end: " << p1.second << std::endl; 
    
      std::vector<int> ivec2 = {1,0,-2,-2,-3}; 
      auto p2 = find_max_product_subarray(ivec2);
      std::cout << "start: " << p2.first << ", end: " << p2.second << std::endl; 
    
      return 0; 
    }
    

  • Mod

    Ich verstehe die Aufgabe wohl falsch 😕

    auto find_max_product_subarray(std::vector<int> const& vec) { 
        long long prod = 1;
        int min = INT_MIN;
        for (auto i : vec) {
            if (i != 0) {
                prod *= i;
                if (i < 0 && i > min)
                    min = i;
            }
        }
    
        if (prod < 0)
            prod /= min;
    
        return prod;            
    }
    

    Dann könnte ich irgendeinen Algo für Maximal Sum Subarray abschreiben und wäre fertig.

    Scheint eine Totgeburt zu sein, die Idee. Du bekommst doch sofort Ungenauigkeiten die sich auch noch akkumulieren. Das muss nicht sein.



  • hier moch mal die aufgabenstellung:
    Find the contiguous subarray within an array (containing at least one number) which has the largest product.

    For example, given the array [2,3,-2,4],
    the contiguous subarray [2,3] has the largest product = 6.



  • bitte um feedback!



  • ArnoldSchw schrieb:

    bitte um feedback!

    Die Idee sieht richtig aus und es scheint zu stimmen, wenn ich currProd mit 1 initialisiere und in der zweiten for-Schleife start und end vertausche.

    Du musst allerdings zweimal über das Array iterieren, während meine Lösung nur mit einmal auskommt (und natürlich 40 Zeilen vs 15).

    @Arcoth: Es geht um ein "contiguous subarray", nicht irgendeine beliebige "subsequence".

    Arcoth schrieb:

    Dann könnte ich irgendeinen Algo für Maximal Sum Subarray abschreiben und wäre fertig.

    Scheint eine Totgeburt zu sein, die Idee. Du bekommst doch sofort Ungenauigkeiten die sich auch noch akkumulieren. Das muss nicht sein.

    Ist halt die typische Idee von einem Bibliotheken-Anwender, der den unterliegenden Algorithmus nicht kennt. Man kann im Algorithmus einfach plus mit mal ersetzen. Wäre vermutlich die beste Lösung, wenn auch Zahlen erlaubt sind, die im Betrag zwischen 0 und 1 liegen.



  • @mapros: kannst du erklaeren wie deinen algo erklaeren?


Anmelden zum Antworten