给定一个带有 +ve 和 -ve integer 的数组，找到最大和，这样你就不能跳过 2 个连续的元素（即你必须至少选择其中一个才能向前移动）。
例如：-
10、20、30、-10、-50、40、-50、-1、-3
输出：10+20+30-10+40-1 = 89
问问题
15605 次
12 回答
8
这个问题可以使用动态规划方法来解决。
设arr为给定数组，opt为存储最优解的数组。 opt[i]是从元素 i 开始可以得到的最大总和，包括元素 i。
opt[i] = arr[i] + (some other elements after i)
现在为了解决这个问题，我们向后迭代数组arr，每次都存储答案opt[i]。由于我们不能跳过 2 个连续元素，因此必须将元素 i+1或元素 i+2包含在opt[i]中。
所以对于每个 i，opt[i] = arr[i] + max(opt[i+1], opt[i+2])
看这段代码就明白了：
int arr[n]; // array of given numbers. array size = n.
nput(arr, n); // input the array elements (given numbers)
int opt[n+2]; // optimal solutions.
memset(opt, 0, sizeof(opt)); // Initially set all optimal solutions to 0.
for(int i = n-1; i >= 0; i--) {
opt[i] = arr[i] + max(opt[i+1], opt[i+2]);
}
ans = max(opt[0], opt[1]) // final answer.
观察opt数组有n+2 个元素。这是为了避免在我们尝试访问最后一个元素(n-1)的opt[i+1]和opt[i+2]时出现非法内存访问异常（内存超出范围） 。
于 2017-03-01T05:25:58.013 回答
7
使用可以解决此问题的重复：
dp[i] = max(dp[i - 1] + a[i], <- take two consecutives
dp[i - 2] + a[i], <- skip a[i - 1])
基本案例留作练习。
于 2015-03-24T15:45:51.797 回答
2
如果您看到 +ve 整数，则将其添加到总和中。如果您看到一个负整数，则检查下一个最大的整数选择并将其添加到总和中。
10、20、30、-10、-50、40、-50、-1、-3
为此添加 10, 20, 30, max(-10, -50), 40 max(-50, -1) 并且因为 -3 旁边没有元素，所以丢弃它。
如果它是+ve，最后一个元素将求和。
于 2015-03-26T21:02:00.247 回答
0
答：
我认为这个算法会有所帮助。
1. 创建一个方法，输出特定用户输入数组的最大总和，例如 T[n]，其中 n 表示总数。的元素。
2. 现在此方法将继续添加数组元素，直到它们为正。因为我们想要最大化总和，所以将积极的元素放在后面是没有意义的。
3. 一旦我们的方法遇到一个负元素，它将所有连续的负元素转移到另一个方法，该方法创建一个新的数组 N[i]，这样这个数组将包含我们在 T[n 中遇到的所有连续的负元素] 并返回 N[i] 的最大输出。
这样，我们的主要方法不会受到影响，它会继续添加正元素，每当遇到负元素时，它不会添加它们的实际值，而是添加负元素的连续数组的净最大输出。
例如： T[n] = 29,34,55,-6,-5,-4,6,43,-8,-9,-4,-3,2,78 //这里 n=14
主要方法工作：
29+34+55+（发送数据并从数组的辅助方法[-6，-5，-4]获取值）+6+43+（发送数据并从数组的辅助方法获取值[-8， -9,-4,-3])+2+78
进程以最大输出终止。
辅助方法工作：
{
N[i] = 在需要时从 Main 方法或自身获取数组。这基本上是一种递归方法。
假设 N[i] 具有 N1、N2、N3、N4 等元素。
for i>=3:
现在选择是这样的。
1. 如果我们取 N1，那么我们可以递归左边的数组，即 N[i-1]，它除了 N1 之外的所有元素都以相同的顺序排列。这样净最大输出将为
N1+（递归发送数据并从数组 N[i-1] 的辅助方法中获取值）
2. 如果我们不取 N1，那么我们不能跳过 N2。所以，Now 算法就像第一选择，但从 N2 开始。因此，在这种情况下，最大输出将为
N2+（递归地从数组 N[i-2] 的辅助方法发送数据并获取值）。这里 N[i-2] 是一个数组，包含除 N1 和 N2 之外的所有 N[i] 元素，顺序相同。
终止：当我们留下大小为一的数组（对于 N[i-2] ）时，我们必须选择该特定值作为没有选项。
递归最终将产生最大输出，我们必须最终选择那个更多的输出。并将最大输出重定向到任何需要的地方。
对于 i=2：
我们必须选择
对于 i=1 更大的值：
我们当然可以跳过该值。
所以在这种情况下，最大输出将为 0。
}
于 2015-03-24T17:07:55.163 回答
0
简单的解决方案：跳过扭曲:)。如果连续 -ve，则跳过 i & i+1 中的最小数字。有条件检查直到 n-2 个元素并检查最后一个元素。
int getMaxSum(int[] a) {
int sum = 0;
for (int i = 0; i <= a.length-2; i++) {
if (a[i]>0){
sum +=a[i];
continue;
} else if (a[i+1] > 0){
i++;
continue;
} else {
sum += Math.max(a[i],a[i+1]);
i++;
}
}
if (a[a.length-1] > 0){
sum+=a[a.length-1];
}
return sum;
}
于 2019-12-17T09:24:40.173 回答
0
正确的重现如下：
dp[i] = max(dp[i - 1] + a[i], dp[i - 2] + a[i - 1])
第一种情况是我们选择第 i 个元素。第二种情况是我们跳过第 i 个元素的情况。在第二种情况下，我们必须选择第 (i-1) 个元素。
IVlad 的答案的问题是它总是选择第 i 个元素，这可能导致错误的答案。
于 2020-01-25T13:54:46.163 回答
0
n = arr.length()。在数组末尾附加一个 0 来处理边界情况。答案：大小为 n+1 的 int 数组。ans[i] 将存储数组 a[0...i] 的答案，其中 a[i] 包含在答案总和中。现在，
ans[0] = a[0]
ans[1] = max(a[1], a[1] + ans[0])
for i in [2,n-1]:
ans[i] = max(ans[i-1] , ans[i-2]) + a[i]
最终答案是 [n]
于 2018-04-13T16:01:23.400 回答
0
我认为这个答案会对你有所帮助。
给定数组：
Given:- 10 20 30 -10 -50 40 -50 -1 -3
Array1:-10 30 60 50 10 90 40 89 86
Array2:-10 20 50 40 0 80 30 79 76
取最大值array1[n-1],array1[n],array2[n-1],array2[n] i.e 89(array1[n-1])
算法：-
- 为 array1 值分配一个
rray1[0]=a[0],array1=a[0]+a[1]和array2[0]=a[0],array2[1]=a[1]。 计算从 2 到 n 的 array1 值是
array1[i-1]+a[i]or之和的最大值array1[i-2]+a[i]。for loop from 2 to n{ array1[i]=max(array1[i-1]+a[i],array1[i-2]+a[i]); }array2[i-1]+a[i]同样，对于从 2 到 n 的 array2 值是或的总和的最大值array2[i-2]+a[i].for loop from 2 to n{ array2[i]=max(array2[i-1]+a[i],array2[i-2]+a[i]); }最后找到最大值
array1[n-1],array[n],array2[n-1],array2[n]；int max(int a,int b){ return a>b?a:b; } int main(){ int a[]={10,20,30,-10,-50,40,-50,-1,-3}; int i,n,max_sum; n=sizeof(a)/sizeof(a[0]); int array1[n],array2[n]; array1[0]=a[0]; array1[1]=a[0]+a[1]; array2[0]=a[0]; array2[1]=a[1]; for loop from 2 to n{ array1[i]=max(array1[i-1]+a[i],array1[i-2]+a[i]); array2[i]=max(array2[i-1]+a[i],array2[i-2]+a[i]); } --i; max_sum=max(array1[i],array1[i-1]); max_sum=max(max_sum,array2[i-1]); max_sum=max(max_sum,array2[i]); printf("The max_sum is %d",max_sum); return 0; }
Ans: max_sum 是 89
于 2017-02-19T17:28:54.287 回答
0
这个问题可以使用包含，排除方法来解决。
对于第一个元素，include = arr[0], exclude = 0.
对于其余元素：
nextInclude = arr[i]+max(include, exclude)
nextExclude = include
include = nextInclude
exclude = nextExclude
最后，ans = Math.max(include,exclude).
类似的问题可以参考（不一样）=> https://www.youtube.com/watch?v=VT4bZV24QNo&t=675s&ab_channel=Pepcoding。
于 2021-08-29T13:52:31.447 回答
0
设数组大小为 N，索引为 1...N
令 f(n) 为函数，它提供子数组 (1...n) 的最大和的答案，使得没有两个剩余元素是连续的。
f(n) = max (a[n-1] + f(n-2), a(n) + f(n-1))
在第一个选项中，即 - {a[n-1] + f(n-2)}，我们将离开最后一个元素，并且由于所给出的条件选择倒数第二个元素。
在第二个选项中，即 - {a(n) + f(n-1)} 我们正在选择子数组的最后一个元素，因此我们可以选择/取消选择倒数第二个元素。
现在从基本情况开始：
f(0) = 0 [Subarray (1..0) doesn't exist]
f(1) = (a[1] > 0 ? a[1] : 0); [Subarray (1..1)]
f(2) = max( a(2) + 0, a[1] + f(1)) [Choosing atleast one of them]
展望未来，我们可以计算任何 f(n)，其中 n = 1...N，并将它们存储起来以计算下一个结果。是的，很明显，案例 f(N) 会给我们答案。
Time complexity o(n)
Space complexity o(n)
于 2017-04-11T05:24:03.173 回答
0
如果你想避免使用动态规划
- 要找到最大和，首先，您必须将所有正数相加。
我们将只跳过负面元素。由于我们不允许跳过 2 个连续的元素，我们将把所有连续的 负元素放在一个临时数组中，并且可以使用如下定义的 sum_odd_even 函数计算出交替元素的最大总和。
然后我们可以将所有此类临时数组的最大值添加到我们所有正数的总和中。最终的总和将为我们提供所需的输出。
代码：
def sum_odd_even(arr):
sum1 = sum2 = 0
for i in range(len(arr)):
if i%2 == 0:
sum1 += arr[i]
else:
sum2 += arr[i]
return max(sum1,sum2)
input = [10, 20, 30, -10, -50, 40, -50, -1, -3]
result = 0
temp = []
for i in range(len(input)):
if input[i] > 0:
result += input[i]
if input[i] < 0 and i != len(input)-1:
temp.append(input[i])
elif input[i] < 0:
temp.append(input[i])
result += sum_odd_even(temp)
temp = []
else:
result += sum_odd_even(temp)
temp = []
print result
于 2018-06-15T12:09:48.937 回答
0
public static void countSum(int[] a) {
int count = 0;
int skip = 0;
int newCount = 0;
if(a.length==1)
{
count = a[0];
}
else
{
for(int i:a)
{
newCount = count + i;
if(newCount>=skip)
{
count = newCount;
skip = newCount;
}
else
{
count = skip;
skip = newCount;
}
}
}
System.out.println(count);
}
}
于 2017-02-25T07:24:55.323 回答