Максимальная сумма непоследовательных элементов

Question

Учитывая массив положительных целых чисел, каков наиболее эффективный алгоритм для поиска непоследовательных элементов из этого массива, которые при сложении дают максимальную сумму?

Answer 1

Динамическое программирование? Для массива A[0..n] пусть M(i) будет оптимальным решением с использованием элементов с индексами 0..i. Затем M(-1) = 0 (используется в повторении), M(0) = A[0] и M(i) = max(M(i - 1), M(i - 2) + A[i]) for i = 1, ..., n. M(n) - это решение, которое мы хотим. Это O (n). Вы можете использовать другой массив для хранения того, какой выбор сделан для каждой подзадачи, и таким образом восстановить фактические выбранные элементы.

Answer 2

Пусть A будет заданным массивом, а Sum будет другим массивом, так что Sum[i] представляет максимальную сумму непоследовательных элементов из arr[0]..arr[i].

. Мы имеем:

Sum[0] = arr[0]
Sum[1] = max(Sum[0],arr[1])
Sum[2] = max(Sum[0]+arr[2],Sum[1])
...
Sum[i] = max(Sum[i-2]+arr[i],Sum[i-1]) when i>=2

Если size - это количество элементов в arr, то sum[size-1] будет ответом.

Можно написать простой рекурсивный метод в порядке сверху вниз как:

int sum(int *arr,int i) {
        if(i==0) {
                return arr[0];
        }else if(i==1) {
                return max(arr[0],arr[1]);
        }
        return max(sum(arr,i-2)+arr[i],sum(arr,i-1));
}

Приведенный выше код очень неэффективен, поскольку он выполняет исчерпывающие повторяющиеся рекурсивные вызовы.Чтобы избежать этого, мы используем запоминание, используя вспомогательный массив с именем sum:

int sum(int *arr,int size) {
        int *sum = malloc(sizeof(int) * size);
        int i;

        for(i=0;i<size;i++) {
                if(i==0) {
                        sum[0] = arr[0];
                }else if(i==1) {
                        sum[1] = max(sum[0],arr[1]);
                }else{
                        sum[i] = max(sum[i-2]+arr[i],sum[i-1]);
                }
        }    
        return sum[size-1];
}

, который равен O(N) в пространстве и времени.

Answer 3

O (N) во времени и O (1) в пространстве (DP) решение:

int dp[2] = {a[0], a[1]};
for(int i = 2; i < a.size(); i++)
{
    int temp = dp[1];
    dp[1] = dp[0] + a[i];
    dp[0] = max(dp[0], temp);
}    
int answer = max(dp[0], dp[1]);

Answer 4

Решение @Ismail Badawi не работает в следующем случае: Давайте возьмем массив: 8, 3, 1, 7 Тогда в этом случае алгоритм возвращает max sum = 9, тогда как оно должно быть 15.

Решением для ее исправления является массив A[0..n], пусть M(i) будет оптимальным решением с использованием элементов с индексами 0..i. Тогда M(0) = A[0] и M(i) = max(M(i - 1), M(i - 2) + A[i], M(i-3) + A[i]) for i = 3, ..., n. M(n) - это решение, которое мы хотим. Это O (n).

Answer 5

/**
 * Given an array of positive numbers, find the maximum sum of elements such
 * that no two adjacent elements are picked
 * Top down dynamic programming approach without memorisation.
 * An alternate to the bottom up approach.
 */

public class MaxSumNonConsec {

public static int maxSum(int a[], int start, int end) {
    int maxSum = 0;

    // Trivial cases
    if (start == end) {
        return a[start];
    } else if (start > end) {
        return 0;
    } else if (end - start == 1) {
        return a[start] > a[end] ? a[start] : a[end];
    } else if (start < 0) {
        return 0;
    } else if (end >= a.length) {
        return 0;
    }

    // Subproblem solutions, DP
    for (int i = start; i <= end; i++) {
        int possibleMaxSub1 = maxSum(a, i + 2, end);
        int possibleMaxSub2 = maxSum(a, start, i - 2);

        int possibleMax = possibleMaxSub1 + possibleMaxSub2 + a[i];
        if (possibleMax > maxSum) {
            maxSum = possibleMax;
        }
    }

    return maxSum;
}

public static void main(String args[]) {
    int a[] = { 8, 6, 11, 10, 11, 10 };
    System.out.println(maxSum(a, 0, a.length - 1));
}
}

Answer 6

int nonContigousSum(vector<int> a, int n) {
    if (n < 0) {
        return 0;
    }
    return std::max(nonContigousSum(a, n - 1), nonContigousSum(a, n - 2) + a[n]);
}

это рекурсивный подход, с помощью которого мы можем решить этот вопрос ОПТИМАЛЬНАЯ ПОДСТРУКТУРА ХОЛДИНГ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. Здесь мы рассматриваем два случая: в первом мы исключаем a [n], а во втором мы включаем a [n] и возвращаем максимум из этих найденных подслучай. Мы в основном находим все подмножества массива и возвращаем длину несмежного массива с максимальной суммой. Используйте табуляцию или памятку для избежания тех же подзадач.

Answer 7

Мое решение - O (N) время и O (1) пространство.

private int largestSumNonConsecutive(int[] a) {
    return largestSumNonConsecutive(a, a.length-1)[1];
}
private int[] largestSumNonConsecutive(int[] a, int end) {  //returns array largest(end-1),largest(end)
    if (end==0) return new int[]{0,a[0]};

    int[] largest = largestSumNonConsecutive(a, end-1);
    int tmp = largest[1];
    largest[1] = Math.max(largest[0] + a[end], largest[1]);
    largest[0] = tmp;

    return largest;
}

Answer 8

Другая реализация Java (работает за линейное время)

public class MaxSum {

private static int ofNonConsecutiveElements (int... elements) {
    int maxsofar,maxi2,maxi1;

    maxi1 = maxsofar = elements[0];
    maxi2 = 0;

    for (int i = 1; i < elements.length; i++) {
        maxsofar =  Math.max(maxi2 + elements[i], maxi1);
        maxi2 =  maxi1;
        maxi1 = maxsofar;
    }
    return maxsofar;        
}

public static void main(String[] args) {
    System.out.println(ofNonConsecutiveElements(6, 4, 2, 8, 1));
}
}

Answer 9

Решение для динамического программирования является самым элегантным из всех. И это служит для любого значения расстояния между двумя числами, которое не должно учитываться. Но для k = 1, который предназначен для ограничения последовательных чисел, я попытался использовать возврат.

Существуют различные шаблоны для сравнения на максимальную сумму. Ниже приведен список:

Number of patterns for 1 = 1    
[1]
Number of patterns for 2 = 2    
[1][2]
Number of patterns for 3 = 2
[1, 3][2]
Number of patterns for 4 = 3
[1, 3][1, 4][2, 4]
Number of patterns for 5 = 4
[1, 3, 5][1, 4][2, 4][2, 5]
Number of patterns for 6 = 5
[1, 3, 5][1, 3, 6][1, 4, 6][2, 4, 6][2, 5]
Number of patterns for 7 = 7
[1, 3, 5, 7][1, 3, 6][1, 4, 6][1, 4, 7][2, 4, 6][2, 4, 7][2, 5, 7]
Number of patterns for 8 = 9
[1, 3, 5, 7][1, 3, 5, 8][1, 3, 6, 8][1, 4, 6, 8][1, 4, 7][2, 4, 6, 8][2, 4, 7][2, 5, 7][2, 5, 8]
Number of patterns for 9 = 12
[1, 3, 5, 7, 9][1, 3, 5, 8][1, 3, 6, 8][1, 3, 6, 9][1, 4, 6, 8][1, 4, 6, 9][1, 4, 7, 9][2, 4, 6, 8][2, 4, 6, 9][2, 4, 7, 9][2, 5, 7, 9][2, 5, 8] 

Ниже приведен код в Java:

public class MaxSeqRecursive {

    private static int num = 5;
    private static int[] inputArry = new int[] { 1,3,9,20,7 };
    private static Object[] outArry;
    private static int maxSum = 0;

    public static void main(String[] args) {

        List<Integer> output = new ArrayList<Integer>();
        output.add(1);
        convert(output, -1);
        for (int i = 0; i < outArry.length; i++) {
            System.out.print(outArry[i] + ":");
        }

        System.out.print(maxSum);
    }

    public static void convert( List<Integer> posArry, int prevValue) {

        int currentValue = -1;

        if (posArry.size() == 0) {
            if (prevValue == 2) {
                return;
            } else {
                posArry.add(2);
                prevValue = -1;
            }

        }

        currentValue = (int) posArry.get(posArry.size() - 1);

        if (currentValue == num || currentValue == num - 1) {
            updateMax(posArry);
            prevValue = (int) posArry.get(posArry.size() - 1);
            posArry.remove(posArry.size() - 1);
        } else {
            int returnIndx = getNext(posArry, prevValue);
            if (returnIndx == -2)
                return;

            if (returnIndx == -1) {
                prevValue = (int) posArry.get(posArry.size() - 1);
                posArry.remove(posArry.size() - 1);
            } else {
                posArry.add(returnIndx);
                prevValue = -1;
            }
        }
        convert(posArry, prevValue);
    }

    public static int getNext( List<Integer> posArry, int prevValue) {
        int currIndx = posArry.size();
        int returnVal = -1;
        int value = (int) posArry.get(currIndx - 1);

        if (prevValue < num) {
            if (prevValue == -1)
                returnVal = value + 2;
            else if (prevValue - value < 3)
                returnVal = prevValue + 1;
            else
                returnVal = -1;
        }

        if (returnVal > num)
            returnVal = -1;

        return returnVal;
    }

    public static void updateMax(List posArry) {
        int sum = 0;
        for (int i = 0; i < posArry.size(); i++) {
            sum = sum + inputArry[(Integer) posArry.get(i) - 1];
        }
        if (sum > maxSum) {
            maxSum = sum;
            outArry = posArry.toArray();
        }
    }
}

Time complexity: O( number of patterns to be compared) 

Answer 10

IIUC: скажем, ваш массив равен 1,2,3,4,5, тогда 3 + 5 будет «правильным», а 4 + 5 - нет, это означает, что вам придется найти самые большие числа и проверить, являются ли они последовательными , Таким образом, алгоритм должен был бы использовать второй массив, для количества элементов, которое вам нужно добавить, который вы заполняете, пересекая исходный массив и находя самые большие непоследовательные целые числа, затем складываете это.

Для приведенного выше массива я предполагаю [1,3], [1,4], [1,5], [1,3,5], [2,4], [2,5], [3, 5] будут действительными непоследовательными целыми числами, которые будут суммироваться, максимальная сумма будет 9 в этом случае [1,3,5]. Итак, чтобы адаптировать вышеупомянутый алгоритм, я бы предложил вам пройтись по массиву, используя несколько временных массивов, чтобы найти все непоследовательные целочисленные списки, а затем проверить, какой из них самый большой. Имейте в виду, что «большинство элементов» не означает «самая большая сумма».