Учитывая массив положительных целых чисел, какой наиболее эффективный алгоритм найдет непоследовательные элементы из этого массива, которые при объединении дают максимальную сумму?
Динамическое программирование? Для массива 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). Вы можете использовать другой массив, чтобы сохранить, какой выбор сделан для каждой подзадачи, и таким образом восстановить выбранные фактические элементы.
Пусть 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));
}
Вышеприведенный код очень неэффективен, так как он делает исчерпывающие повторяющиеся рекурсивные вызовы. Чтобы избежать этого, мы используем memoization с помощью вспомогательного массива с именем 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) как в пространстве, так и во времени.
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]);
/**
* 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));
}
}
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]. Итак, чтобы адаптировать алгоритм выше, я бы предложил вам пройти через массив, используя несколько временных массивов, чтобы найти все непоследовательные целые списки, а затем проверить, какой из них самый большой. Имейте в виду, что "большинство элементов" не означает "наибольшая сумма".
Динамическое программирующее решение является самым элегантным из всех. И он служит для любого значения расстояния между двумя числами, которые не следует рассматривать. Но для 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)
Другая реализация 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));
}
}
Мое решение - это время 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;
}
Решение @Ismail Badawi, похоже, не работает в следующем случае: Возьмем массив: 8, 3, 1, 7 Тогда в этом случае algo возвращает 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).
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]);
}
это рекурсивный подход, с помощью которого мы можем решить этот вопрос (ОПТИМАЛЬНАЯ ПОДСТРУКТУРА HALLMARK ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. Здесь мы рассматриваем два случая, в первом мы исключаем a [n], а во втором мы включаем a [n] и вернуть максимальное количество найденных подслучайников. Мы в основном находим все подмножества массива и возвращаем длину несмежного массива с максимальной суммой. Используйте табуляции или запоминания для избежания тех же подзадач.
Составьте список чисел, которые представляют собой нечетные или четные суммы, соответствующие каждому числу; например для ввода [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
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).
Довольно наивная, но полная реализация. Уравнение рекурсии 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());
}
}
Вот версия С# для справки (вы можете ссылаться на: http://dream-e-r.blogspot.com/2014/07/maximum-sum-of-non-adjacent-subsequence.html):
В целях решения проблемы с использованием динамического программирования должно быть решение, которое имеет оптимальную субструктуру и перекрывающиеся свойства подзадач. И текущая проблема имеет оптимальное свойство субструктуры. Скажем, f (i) определяется как максимальная сумма подпоследовательности не соседних элементов для элементов "i", тогда
f (i) = 0, если я = 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);
}
}
}
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));
}
Пенни от меня.
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});
}
}