Так что я делал эту задачу на алгоритмах, где мне нужно было найти максимальную сумму непоследовательных элементов в массиве, подходя к подходу DP. Хотя эту сумму легко получить, я не могу понять, как получить отдельные подзадачи (или числа, образующие максимальную сумму).
Я попытался проверить, является ли вставляемый элемент соседним или нет.
int MaxSum(int arr[], int n) {
int a[n/2];
int inc = arr[0];
int exc = 0;
int exc_n;
int i, pos = -1, j = 0;
for (i = 1; i < n; i++)
{
if (inc > exc)
{
exc_n = inc;
if (pos + 1 != i){
a[j] = arr[i];
j++;
pos = i;
}
else
{
exc_n = exc;
}
inc = exc + arr[i];
exc = exc_n;
}
return ((inc > exc) ? inc : exc);
}
Мне нужно вернуть элементы, которые образуют максимальную сумму, которая удовлетворяет условию «несмежность». Что я делаю не так и что я могу сделать, чтобы продолжить?