Максимальная сумма несмежных элементов массива - PullRequest
0 голосов
/ 17 апреля 2019

Так что я делал эту задачу на алгоритмах, где мне нужно было найти максимальную сумму непоследовательных элементов в массиве, подходя к подходу 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); 
}

Мне нужно вернуть элементы, которые образуют максимальную сумму, которая удовлетворяет условию «несмежность». Что я делаю не так и что я могу сделать, чтобы продолжить?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...