AlexSetup
@AlexSetup
Python

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

Реализовал алгоритм поиска максимального подмассива:
#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;
}

Этот код не работает. Как можно исправить данную программу, чтобы она выводила верный ответ?
Заранее спасибо!
  • Вопрос задан
  • 187 просмотров
Решения вопроса 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.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы