значение возврата, которое было выбрано
У меня есть программа на C ++, которая вычисляет максимум массива при условии, что два последовательных элемента массива не могут быть взяты.
Например:
7 3 4 6 приведет к ответу 13. Здесь мы выбрали 7 и 6 для оптимального максимума.
Вот моя рекурсивная программа для этого.
#include <iostream>
using namespace std;
int n;
int findMax(int x,int ar[])
{
if(x < n)
return max( ar[x]+findMax(x+2,ar), findMax(x+1,ar));
return 0;
}
int main(){
int ar[]={1,7,4,4,9,5,12};
n = sizeof(ar)/sizeof(ar[0]);
cout<<findMax(0,ar);
return 0;
}
тем не мение Меня больше интересуют индексы массива, которые были выбраны для этой цели моей программой. Как я могу сделать это эффективно.
В приведенной выше программе ответ должен быть 1,4,6 как мы выбрали 1-й, 4-й и 6-й элемент массива для максимума.
Замечания: Я использую индексирование на основе 0.
Благодарю.
Решение
Отношение рекуррентности R (k) для максимальной суммы первых k элементов массива (без смежных членов):
R(0) = 0, R(1) = max(0, a[0])
R(k) = max(a[k] + R(k-2), R(k-1))
Это почти то же самое повторение, которое вы используете в своем коде, но в вашем коде ваша функция возвращает максимальную сумму элементов k и позже.
В любом случае, вы можете построить таблицу этих значений за линейное время, используя динамическое программирование. В псевдокоде:
R = new array of length n+1
R[0] = 0
R[1] = max(0, a[0])
for i = 2 .. n
R[i] = max(a[i-1] + R[i-2], R[i-1])
Если вы просто хотите получить максимальную сумму, вы можете вернуть R [n]. Но вы также можете легко восстановить индексы. В псевдокоде:
indices(a, R):
result = new empty vector
i = n
while i > 0
if (i == 1 and a[0] > 0) or R[i] == a[i-1] + R[i-2]
result.push_back(i-1)
i -= 2
else
i -= 1
Вам придется повернуть вспять result чтобы получить индексы в порядке возрастания.
Другие решения
Это определенно не самое эффективное решение, но, вероятно, с наименьшими усилиями по реализации:
#include <iostream>
#include <vector>
using namespace std;
int n;
pair<int, vector<int> > findMax(int x, int ar[])
{
if (x < n) {
pair<int, vector<int> > max1 = findMax(x + 2, ar);
const pair<int, vector<int> > max2 = findMax(x + 1, ar);
max1.first += ar[x];
max1.second.insert(max1.second.begin(), x);
return max1.first >= max2.first ? max1 : max2;
}
return make_pair(0, vector<int>());
}
ostream& operator<<(ostream &out, const vector<int> &vec)
{
const char *sep = "";
for (int value : vec) {
out << sep << value; sep = ", ";
}
return out;
}
int main()
{
int ar[]={1,7,4,4,9,5,12};
n = sizeof ar / sizeof *ar;
const pair<int, vector<int> > maxAr = findMax(0, ar);
cout << maxAr.first << '\n'
<< maxAr.second << '\n';
return 0;
}
Выход:
28
1, 4, 6
Таким образом, возвращаемое значение увеличивается с std::vector<int> который содержит используемые индексы помимо текущей суммы.
std::max() можно использовать, если я предоставлю подходящий (перегруженный) operator<() за std::pair<int, std::vector<int> >, Чтобы не усложнять, я просто заменил std::max() соотв. состояние.
Я думаю, что приведенный ниже код удовлетворит ваши потребности.
#include<bits/stdc++.h>
using namespace std;
int n;
void findMax(int arr[], int in, pair< int, vector<int> > tempStore,
pair< int, vector<int> > &resStore) {
if(in >=n) {
if(resStore.first < tempStore.first) {
resStore.first = tempStore.first;
resStore.second = tempStore.second;
}
return;
}
findMax(arr, in+1, tempStore, resStore);
tempStore.first += arr[in];
tempStore.second.push_back(in);
findMax(arr, in+2, tempStore, resStore);
}
int main() {
int ar[]={1,7,4,4,9,5,12};
n = sizeof(ar)/sizeof(ar[0]);
pair< int, vector<int> > resStore, tempStore;
findMax(ar, 0,tempStore,resStore);
cout<<"Result Value: "<<resStore.first;
cout<<"\nResult Index:\n";
for(int i=0; i<resStore.second.size(); i++) {
cout<<resStore.second[i]<<" ";
}
return 0;
}