Maximum Product Subarray


  • Mod

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

    Danke, das habe ich mittlerweile auch deduziert. Kein Problem. Wie wäre es mit

    template <typename RandomAccessIter>
    auto find_max_product_subarray(RandomAccessIter first, RandomAccessIter last)
      -> typename std::iterator_traits<RandomAccessIter>::value_type {
    	auto max_prod = *std::max_element(first, last);
    	if (max_prod < 1) return max_prod;
    
    	auto size = last - first;
    
    	for (std::size_t index = 0; index != size;) {
    		decltype(max_prod) prod = 1,
    		                   min = std::numeric_limits<decltype(min)>::min();
    		do {
    			if (first[index] == 0) {++index; break;}
    			auto&& i = first[index];
    			prod *= i;
    			if (i < 0 && i > min)
    				min = i;
    		} while(++index != size);
    
    		max_prod = std::max(max_prod, prod < 0? prod/min : prod);
    	}
    
    	return max_prod;
    }
    

    ?

    Ist halt die typische Idee von einem Bibliotheken-Anwender, der den unterliegenden Algorithmus nicht kennt.

    Das nimm am besten zurück, denn Volkard ist nicht so einer.



  • Arcoth schrieb:

    wie wäre es mit

    Das ist doch nicht O(n)?

    Arcoth schrieb:

    Ist halt die typische Idee von einem Bibliotheken-Anwender, der den unterliegenden Algorithmus nicht kennt.

    Das nimm am besten zurück, denn Volkard ist nicht so einer.

    lol, da war auch nicht von Volkard die Rede ... 🤡


  • Mod

    Swordfish schrieb:

    Arcoth schrieb:

    wie wäre es mit

    Das ist doch nicht O(n)?

    ... weil ich eine verschachtelte Schleife hab'? Hast du überhaupt den Code gelesen!?



  • Ouch. Sorry.


  • Mod

    Swordfish schrieb:

    Ouch. Sorry.

    Hat Volkard auch schon mal gefragt, aber per PM 🕶



  • @Arcoth: kannst du deinen algo erklaeren?



  • Arcoth schrieb:

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

    Danke, das habe ich mittlerweile auch deduziert. Kein Problem. Wie wäre es mit [...]

    Du hast auch zwei Bugs, einen in der Implementierung und einen zweiten in der Grundidee

    {-2,-2} // gibt bei mir -2 aus
    {2,-1,2} // gibt bei mir 4 aus, aber das ist nicht möglich
    

    @ArnoldSchw: Ich behalte meinen Algorithmus noch ein bisschen "geheim" (der Code ist ja vorhanden), ich finde es witzig, zu sehen was andere versuchen.



  • Arcoth schrieb:

    Volki 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.

    Jo, klar.
    Scanline-Algos und dynamische Programmierung sind in meinem Kopf total panne abgelegt, die kann ich stets nicht reinklimpern, ohne vorher auf Papier ein paar Beispiele gemacht zu haben.
    Dächte, von + zu * könnten ich oder der TO zur Not an + denken (nachschauen) und * machen. Zu diesem Zwecke auch der Link.


  • Mod

    Huch, ich hab leider den Code mit zu wenigen Änderungen übernommen, kann auch AFAICS nicht direkt gefixed werden.



  • @mapros: mein algo ist doch recht lesbar und funktioniert!?
    bitte das konzept erklaeren...


  • Mod

    @mapros: Dein Algorithmus versagt bei { -1 }

    ok, man könnte evtl. eine leere Sequenz zulassen und dieser willkürlich den Wert 0 geben; das geht aus AUfgabenstellung nicht klar hervor.


Anmelden zum Antworten