Maximum Product Subarray

happystudent

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?

happystudent

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; 
}

Columbo

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?

Columbo

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

Swordfish

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

Columbo

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!?

Swordfish

Ouch. Sorry.

Columbo

Swordfish schrieb:

Ouch. Sorry.

Hat Volkard auch schon mal gefragt, aber per PM

@Arcoth: kannst du deinen algo erklaeren?