给定一个正整数数组，如何找到非连续元素使它们相加的和最大？请提供最高效的算法。
17个回答
52
动态规划？给定一个数组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])，i = 1, ..., n。 M(n)是我们想要的解。这是O(n)。您可以使用另一个数组来存储每个子问题所做的选择，并恢复所选的实际元素。
- Ismail Badawi
1
2我还想存储产生最大总和的元素的索引，我该怎么做？ - Lakshya Munjal
25
设给定数组为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)。
- codaddict
4
可以避免 O(N) 的额外空间，我们只需要在每次迭代结束时使用仅有的 2 个额外变量来跟踪 sum[i - 1] 和 sum[i - 2]。 - algo_freek
这个解决方案针对测试用例“1 2 3 4”的输出结果是6，但实际应该是10。 - David G
1@0x499602D2
6 是正确答案，10 是所有元素的总和，因此在非连续性的约束条件下不可能是正确答案。 - Robin Nabel@RobinNabel 对，我没注意到“非”连续的。 - David G
15
时间复杂度为 O(N)，空间复杂度为 O(1)（动态规划）的解决方案：
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]);
- Pulkit Gupta
5
8如果您能在每行代码中添加一些注释说明其作用就好了。这是一个非常优化和干净的解决方案，但对于一些人来说，它可能过于优雅，需要额外的注释才能理解。 - smaili
2如何找到索引？ - Rasmi Ranjan Nayak
1这个解决方案在我的测试用例中应该是
10，但对于1 2 3 4却给了我6。 - David G问题不够清晰。上述解决方案是为了找到最大子数组，其中没有两个元素是连续的。
上述解决方案不适用于连续和非连续元素都存在的子数组情况。 - hack3r
1@0x499602D2 针对连续元素的情况，那将会有所不同。给出的解决方案是针对非连续元素之和。 - learntogrow-growtolearn
2
/**
* 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));
}
}
- Anurag Kapur
1
2只是补充一下，上面是一个简单的递归实现，没有记忆化。通过将计算的子问题添加到哈希表中，并在计算新的子问题之前在哈希表中进行检查，可以通过缓存/记忆化重复子问题的解来改善其运行时间。 - Anurag Kapur
2
@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）。- user4090410
1
Ismail的算法为您的测试用例提供了正确的答案。m [0] = m [1] = 8，m [2] = 9，m [3] = max（m [2]，m [1] + 7）= 15。 - YouCantSeeMe
1
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]并返回找到的这些子情况的最大值。我们基本上在查找数组的所有子集，并返回具有最大总和的非连续数组的长度。使用表格法或备忘录法以避免相同的子问题。
- Akash Chandra
3
不鼓励只提供代码的答案。请查看[帮助]以了解如何正确格式化您的输入。对于C++代码来说，放置“运行代码片段”根本没有意义，是吧？！ - GhostCat
难道不应该是(n-2)而不是(n-1)吗？你是假设数组从索引1开始吗？ - Venkatesh Laguduva
@TechJunkie，谢谢你。我没有读到“非连续”元素的那一部分。 - Akash Chandra
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});
}
}
- Juvenik
1
动态规划解决方案是所有方法中最优美的。它适用于任何不应被考虑的两个数字之间的距离值。但对于k=1，即连续数字约束，我尝试使用回溯法。
有不同的模式可用于比较最大总和。以下是列表：
以下是Java代码：
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)
- user1573193
2
1看起来这个算法不是多项式的，而是指数级别的。随着元素数量的增加，模式呈指数级别增长（0、1、2、2、3、4、5、7、9、12、16、21、28、37、49、65、86、114、151、200、265、351、465、616）。 :-( - user1573193
有趣的是，这个模式与斐波那契数列相似，只是稍作改变：F(n) = F(n-2) + F(n-3) !!!! - user1573193
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;
}
- Fabio Hecht
1
3实际上，这个算法使用 O(n) 的空间，因为对于
largestSumNonConsecutive() 的递归调用会在栈上占用空间。 - j_random_hacker1
另一种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));
}
}
- craftsmannadeem
1
{1,2,13,4,5,9}; 尝试使用此输入，它将返回23而不是22。 - dnxit
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接