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

Question

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

Answer 1

пенни от меня.

public class Problem {

  /**
   * Solving by recursion, top down approach. Always try this recursion approach and then go with
   * iteration. We have to add dp table to optimize the time complexity.
   */
  public static int maxSumRecur(int arr[], int i) {
    if(i < 0) return 0;
    if(i == 0) return arr[0];
    if(i == 1) return Math.max(arr[0], arr[1]);

    int includeIthElement = arr[i] + maxSumRecur(arr, i-2);
    int excludeIthElement = maxSumRecur(arr, i-1);
    return Math.max(includeIthElement, excludeIthElement);
  }

  /**
   * Solving by iteration. Bottom up approach.
   */
  public static void maxSumIter(int arr[]) {
    System.out.println(Arrays.toString(arr));
    int dp[] = new int[arr.length];
    dp[0] = arr[0];
    dp[1] = Math.max(arr[0], arr[1]);

    for(int i=2; i <= arr.length - 1; i++) {
      dp[i] = Math.max(arr[i] + dp[i-2], dp[i-1]);
    }

    System.out.println("Max subsequence sum by Iteration " + dp[arr.length - 1] + "\n");
  }

  public static void maxSumRecurUtil(int arr[]) {
    System.out.println(Arrays.toString(arr));
    System.out.println("Max subsequence sum by Recursion " + maxSumRecur(arr, arr.length - 1) +
        "\n");
  }

  public static void main(String[] args) {
    maxSumRecurUtil(new int[]{5, 5, 10, 100, 10, 5});
    maxSumRecurUtil(new int[]{20, 1, 2, 3});

    maxSumIter(new int[]{5, 5, 10, 100, 10, 5});
    maxSumIter(new int[]{20, 1, 2, 3});

  }

}

Answer 2

public static int maxSumNoAdj(int[] nums){
    int[] dp = new int[nums.length];
    dp[0] = Math.max(0, nums[0]); // for dp[0], select the greater value (0,num[0])
    dp[1] = Math.max(nums[1], Math.max(0, dp[0]));    
    int maxSum = Math.max(dp[0], dp[1]);
    for(int i = 2; i < nums.length; i++){
        int ifSelectCurrent = Math.max(nums[i] + dp[i-2], dp[i-2]);// if select, there are two possible
        int ifNotSelectCurrent = Math.max(dp[i-1], dp[i-2]);        // if not select, there are two posible
        dp[i] = Math.max(ifSelectCurrent, ifNotSelectCurrent);      // choose the greater one
        maxSum = Math.max(dp[i], maxSum);   // update the result
    }
    return maxSum;
}

public static void main(String[] args) {
    int[] nums = {-9, 2, 3, -7, 1, 1};
    System.out.println(maxSumNoAdj(nums));
}

Answer 3

Вот версия C # для справки (вы можете ссылаться на: http://dream -er.blogspot.com / 2014/07 / максимальная сумма несмежных-подпоследовательностей.html ):

Для решения проблемы с использованием динамического программирования должно быть решение, которое имеет оптимальную подструктуру и перекрывающиеся свойства подзадач.И текущая задача имеет оптимальное свойство подструктуры.Скажем, f (i) определяется как максимальная сумма подпоследовательности несмежных элементов для элементов 'i', тогда

f (i) = 0, если i = 0 max (f (i-1), f (i-2) + a [i])

Ниже приведен алгоритм для того же самого (нет, он не может быть решен без инкапсуляции данных в «записи» - я просто предпочел его таким образом) - который должен проиллюстрироватьПриведенная выше идея:

int FindMaxNonAdjuscentSubsequentSum(int[] a)
        {
            a.ThrowIfNull("a");
            if(a.Length == 0)
            {
                return 0;
            }
            Record r = new Record()
            {
                max_including_item = a[0],
                max_excluding_item = 0
            };
            for (int i = 1; i < a.Length; i++)
            {
                var t = new Record();
                //there will be only two cases
                //1. if it includes the current item, max is maximum of non adjuscent sub
                //sequence sum so far, excluding the last item
                t.max_including_item = r.max_excluding_item + a[i];
                //2. if it excludes current item, max is maximum of non adjuscent subsequence sum
                t.max_excluding_item = r.Max;
                r = t;
            }
            return r.Max;
        }

Юнит-тесты

[TestMethod]
        [TestCategory(Constants.DynamicProgramming)]
        public void MaxNonAdjascentSubsequenceSum()
        {
            int[] a = new int[] { 3, 2, 5, 10, 7};
            Assert.IsTrue(15 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 3, 2, 5, 10 };
            Assert.IsTrue(13 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 5, 10, 40, 50, 35 };
            Assert.IsTrue(80 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 1, -1, 6, -4, 2, 2 };
            Assert.IsTrue(9 == this.FindMaxNonAdjuscentSubsequentSum(a));
            a = new int[] { 1, 6, 10, 14, -5, -1, 2, -1, 3 };
            Assert.IsTrue(25 == this.FindMaxNonAdjuscentSubsequentSum(a));
        }

, где

public static int Max(int a, int b)
        {
            return (a > b) ? a : b;
        }
        class Record
        {
            public int max_including_item = int.MinValue;
            public int max_excluding_item = int.MinValue;
            public int Max
            {
                get
                {
                    return Max(max_including_item, max_excluding_item);
                }
            }
        }

Answer 4

Довольно наивная, но полная реализация.Уравнение рекурсии T (n) = n ^ 2 + nT (n-3), что, если я не ошибаюсь, приводит к экспоненциальному времени.(N-3) происходит из-за того, что число не может быть добавлено к себе / предыдущим / следующим числам.

Программа сообщает составной список, который составляет сумму (существует несколько экспоненциально растущих из этих списков, но он просто выбирает один).

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class MaxSumNoAdjacent {

    private static class Sum {
        int sum;
        List<Integer> constituents = new ArrayList<>();

        Sum(int sum, List<Integer> constituents) {
            this.sum = sum;
            this.constituents = constituents;
        }

        @Override
        public String toString() {
            return "sum: " + sum + " " + constituents.toString(); 
        }
    }

    public static Sum maxSum(int[] arr) {
        List<Integer> input = new ArrayList<>();
        for (int i : arr) {
            if (i != Integer.MIN_VALUE) { //Integer.MIN_VALUE indicates unreachability
                input.add(i);
            }
        }

        if (input.size() == 0) {
            return null;
        }

        if (input.size() == 1) {
            List<Integer> constituents = new ArrayList<>();
            constituents.add(input.get(0));
            return new Sum(input.get(0), constituents);
        }

        if (input.size() == 2) {
            int max = Math.max(input.get(0), input.get(1));
            List<Integer> constituents = new ArrayList<>();
            constituents.add(max);
            return new Sum(max, constituents);
        }

        Map<Integer, int[]> numberAndItsReachability = new HashMap<>();
        for (int i = 0; i < input.size(); i++) {
            int[] neighbours = new int[input.size()];
            if (i > 0) {
                neighbours[i-1] = Integer.MIN_VALUE; //unreachable to previous
            }

            if (i < input.size()-1) {
                neighbours[i+1] = Integer.MIN_VALUE; //unreachable to next
            }

            neighbours[i] = Integer.MIN_VALUE; //unreachable to itself

            for (int j = 0; j < neighbours.length; j++) {
                if (neighbours[j] == 0) {
                    neighbours[j] = input.get(j); //remember values of reachable neighbours
                }
            }

            numberAndItsReachability.put(input.get(i), neighbours);
        }

        Sum maxSum = new Sum(Integer.MIN_VALUE, null);
        for (Entry<Integer, int[]> pair : numberAndItsReachability.entrySet()) {
            Sum sumMinusThisNumber = maxSum(pair.getValue()); //call recursively on its reachable neighbours
            if (sumMinusThisNumber != null) {
                int candidateSum = sumMinusThisNumber.sum + pair.getKey();
                if (maxSum.sum < candidateSum) {
                    sumMinusThisNumber.constituents.add(pair.getKey());
                    maxSum = new Sum(candidateSum, sumMinusThisNumber.constituents);
                }
            }

        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr1 = {3,2,5,10,7};
        int[] arr2 = {3,2,7,10};
        int[] arr3 = {5,5,10,40,50,35};
        int[] arr4 = {4,4,4,4};
        System.out.println(maxSum(arr1).toString());
        System.out.println(maxSum(arr2).toString());
        System.out.println(maxSum(arr3).toString());
        System.out.println(maxSum(arr4).toString());
    }

}

Answer 5

public static int findMaxSum(int[] a){
        int sum0=0; //will hold the sum till i-2        
        int sum1=0;//will hold the sum till i-1
        for(int k : a){
            int x=Math.max(sum0+k, sum1);//max(sum till (i-2)+a[i], sum till (i-1))
            sum0=sum1;
            sum1=x;
        }
        return sum1;
    }

Ниже суть алгоритма:

max(max sum till (i-2)+a[i], max sum till (i-1))

O (N) сложность времени иO (1) космическая сложность.

Answer 6

Составьте список чисел, которые на данный момент являются нечетными или четными суммами, соответствующими каждому числу;например, для ввода [1,2,4,1,2,3,5,3,1,2,3,4,5,2] нечетно-четные суммы были бы [1,2,5,3,7,6,12,9,13,11,16,15,21,17]

Теперь перебираем список с жадным суммированием в обратном порядке, но пропускаем те элементы, чья нечетная / четная сумма меньше, чем у ближайших крассматриваемый элемент.

src = [1,2,4,1,2,3,5,3,1,2,3,4,5,2]

odd_even_sums = src[:2]
for i in xrange(2,len(src)):
    odd_even_sums.append(src[i] + odd_even_sums[i-2])

best = []
for i in xrange(len(src)-1,-1,-1):
    if i == 0:
        best.append(i)
    elif odd_even_sums[i-1] > odd_even_sums[i]:
        pass
    elif odd_even_sums[i-1] == odd_even_sums[i]:
        raise Exception("an exercise for the reader")
    else:
        best.append(i)

best.reverse()

print "Best:",",".join("%s=%s"%(b,src[b]) for b in best)
print "Scores:",sum(odd_even_sums[b] for b in best)

Выходы:

Best: 0=1,1=2,2=4,4=2,6=5,8=1,10=3,12=5
Scores: 77