значение возврата, которое было выбрано

У меня есть программа на 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.

Благодарю.

2

Решение

Отношение рекуррентности 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 чтобы получить индексы в порядке возрастания.

0

Другие решения

Это определенно не самое эффективное решение, но, вероятно, с наименьшими усилиями по реализации:

#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() соотв. состояние.

0

Я думаю, что приведенный ниже код удовлетворит ваши потребности.

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