Как исправить данный алгоритм поиска максимального подмассива?

Question

[Alex Setup]

Реализовал алгоритм поиска максимального подмассива:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int Find_Max_Crossing_Subarray(vector<int> A, int low, int mid, int high) {
	int leftsum,sum,maxleft,rightsum,maxright;
	leftsum = -100000000;
	sum = 0;
	for (int i = mid; i >= low; i--) {
		sum += A[i];
		if (sum > leftsum) {
			leftsum = sum;
			maxleft = i;
		}
	}
	rightsum = -1000000000;
	sum = 0;
	for (int j = mid + 1; j <= high; j++) {
		sum += A[j];
		if (sum > rightsum) {
			rightsum = sum;
			maxright = j;
		}
	}
	return (maxleft, maxleft, leftsum + rightsum);
}

int Find_Maximum_Subarray(vector<int>A, int low, int high) {
	int mid;
	int leftsum, rightsum,leftlow,lefthigh,rightlow,righthigh,crosslow,crosshigh,crosssum;
	if (high == low) {
		return (low, high, A[low]);
	}
	else{
		mid = floor((low + high) / 2.0);
		(leftlow, lefthigh, leftsum) = Find_Maximum_Subarray(A, low, mid);
		(rightlow, righthigh, rightsum) = Find_Maximum_Subarray(A, mid + 1, high);
		(crosslow, crosshigh, crosssum) = Find_Max_Crossing_Subarray(A, low, mid, high);
		if (leftsum >= rightsum and leftsum >= crosssum) {
			return (leftlow, lefthigh, leftsum);
		}
		else {
			if (rightsum >= leftsum and rightsum >= crosssum) {
				return (rightlow, righthigh, rightsum);
			}
			else {
				return (crosslow, crosshigh, crosssum);
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	vector <int> A(n);
	vector <int> B;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	int h,t,l;
	h,t,l = Find_Maximum_Subarray(A, 0, n - 1);
	cout <<h<<" "<<t<<" "<<l<<endl;
	system("pause");
	return 0;
}

Этот код не работает. Как можно исправить данную программу, чтобы она выводила верный ответ?
Заранее спасибо!

Comments

[Антон Жилин]

Что значит "максимальный подмассив"? Массивы нельзя сравнивать

[devalone]

return (crosslow, crosshigh, crosssum);
Это так не работает, тут тебе не питон, тем более ты сам указал, что функция возвращает int

int Find_Maximum_Subarray(vector<int>A, int low, int high)

[Alex Setup]

Антон Жилин, В книге Кормена "Алгоритмы. Построение и анализ" данная тема называется "Задача поиска максимального подмассива"

Answer 1

[Mercury13]

1. Учите, что означает операция «запятая». Если вы хотите выдать наружу три числа — так и пишите возвращаемым типом не int, а структуру из трёх чисел.
2. Передавать vector по значению невыгодно, лучше по константной ссылке.

struct ArrayOut {
  int low, high, sum;

  ArrayOut() : low(0), high(0), sum(0) {}
  ArrayOut(int aLow, int aHigh, int aSum) : low(aLow), high(aHigh), sum(aSum) {}
};


ArrayOut Find_Max_Crossing_Subarray(const vector<int>& A, int low, int mid, int high)  { ... }

UPD. Операция «запятая» — это странный хак Си, позволяющий впихнуть несколько операторов туда, где разрешён только один. В основном в цикл for.

Comments

[Alex Setup]

Ну как реализовать первый пункт? Если Вам не трудно не могли бы объяснить

[Mercury13]

struct ArrayOut {
  int low, high, sum;

  ArrayOut() : low(0), high(0), sum(0) {}
  ArrayOut(int aLow, int aHigh, int aSum) : low(aLow), high(aHigh), sum(aSum) {}
};

ArrayOut Find_Max_Crossing_Subarray(const vector<int>& A, int low, int mid, int high)  {}

[devalone]

Alex Setup, либо создай свою структуру и возвращай её:

struct SomeKindOfResult {
  int value;
  double anotherValue;
  std::string yetAnotherValue;
};
SomeKindOfResult getResult(/* args */) 
{
  SomeKindOfResult result;
  // fill result
  return result;
}

Или возвращай tuple например
en.cppreference.com/w/cpp/utility/tuple

[Alex Setup]

Mercury13, Ладно со структурой разобрался. Как тогда можно поменять вторую функцию. Первую исправил как то так:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct ArrayOut {
	int low, high, sum;
};

ArrayOut Find_Max_Crossing_Subarray(vector<int> A, int low, int mid, int high) {
	int leftsum,sum,maxleft,rightsum,maxright;
	leftsum = -100000000;
	sum = 0;
	for (int i = mid; i >= low; i--) {
		sum += A[i];
		if (sum > leftsum) {
			leftsum = sum;
			maxleft = i;
		}
	}
	rightsum = -1000000000;
	sum = 0;
	for (int j = mid + 1; j <= high; j++) {
		sum += A[j];
		if (sum > rightsum) {
			rightsum = sum;
			maxright = j;
		}
	}
	ArrayOut struct_temp;
	struct_temp.low = maxleft;
	struct_temp.high = maxright;
	struct_temp.sum = leftsum + rightsum;
	return struct_temp;
}

[Mercury13]

Alex Setup, Вторая точно так же возвращает тройку low, high, sum — а значит, можно сделать, чтобы она возвращала всё тот же ArrayOut.

Да, и не забудьте второе: вместо (vector<int> A, int low…) лучше (const vector<int> &A, int low…)

[Alex Setup]

Mercury13, А этот кусочек как поменять?

(leftlow, lefthigh, leftsum) = Find_Maximum_Subarray(A, low, mid);
(rightlow, righthigh, rightsum) = Find_Maximum_Subarray(A, mid + 1, high);
(crosslow, crosshigh, crosssum) = Find_Max_Crossing_Subarray(A, low, mid, high);

[Mercury13]

Alex Setup, Ну и, разумеется…

ArrayOut left = Find_Maximum_Subarray(A, low, mid);
…
if (left.sum >= right.sum && left.sum >= cross.sum) { … }

[Mercury13]

Alex Setup,
Если вы к ArrayOut пристроите конструкторы, как я написал, то можно сделать

// БЫЛО
  ArrayOut struct_temp;
  struct_temp.low = maxleft;
  struct_temp.high = maxright;
  struct_temp.sum = leftsum + rightsum;
  return struct_temp;
// СТАЛО
  return ArrayOut(maxleft, maxright, leftsum + rightsum);

[Mercury13]

Alex Setup, Не советую использовать and, or, xor, bitand и прочие альтернативные форы операций. Они служат, чтобы писать на Си на ограниченных клавиатурах. Используйте &&, ||, ^, | соответственно.

[Alex Setup]

Mercury13, Вот поправил я функции вроде. Если Вам не трудно подскажите как концовку поменять
Вот измененный код (концовка не работает)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct ArrayOut {
	int low, high, sum;
};

ArrayOut Find_Max_Crossing_Subarray(vector<int> &A, int low, int mid, int high) {
	int leftsum,sum,maxleft,rightsum,maxright;
	leftsum = -100000000;
	sum = 0;
	for (int i = mid; i >= low; i--) {
		sum += A[i];
		if (sum > leftsum) {
			leftsum = sum;
			maxleft = i;
		}
	}
	rightsum = -1000000000;
	sum = 0;
	for (int j = mid + 1; j <= high; j++) {
		sum += A[j];
		if (sum > rightsum) {
			rightsum = sum;
			maxright = j;
		}
	}
	ArrayOut struct_temp;
	struct_temp.low = maxleft;
	struct_temp.high = maxright;
	struct_temp.sum = leftsum + rightsum;
	return struct_temp;
}

ArrayOut Find_Maximum_Subarray(vector<int> &A, int low, int high) {
	int mid;
	int leftsum, rightsum,leftlow,lefthigh,rightlow,righthigh,crosslow,crosshigh,crosssum;
	if (high == low) {
		ArrayOut X;
		X.low = low;
		X.high = high;
		X.sum = A[low];
		return X;
	}
	else{
		mid = floor((low + high) / 2.0);
		ArrayOut left = Find_Maximum_Subarray(A, low, mid);
		ArrayOut right= Find_Maximum_Subarray(A, mid + 1, high);
		ArrayOut cross = Find_Max_Crossing_Subarray(A, low, mid, high);
		if (left.sum >= right.sum && left.sum >= cross.sum) {
			return left;
		}
		else {
			if (right.sum >= left.sum && right.sum >= cross.sum) {
				return right;
			}
			else {
				return cross;
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	vector <int> A(n);
	vector <int> B;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	ArrayOut B= Find_Maximum_Subarray(A, 0, n - 1);
	cout <<B.low<<" "<<B.high<<" "<<B.sum<<endl;
	system("pause");
	return 0;
}

[Alex Setup]

Mercury13, Все разобрался со всем вопросом. Огромное Вам спасибо за столь огромный совет по C++ и за решение данного вопроса