Java 中不相邻元素的最大总和

在本教程中，我们将讨论如何在 Java 中计算不相邻元素的最大和。输入是一个包含正数的数组 (inptArr[])。

示例 1

输入

int inptArr[] = {15, 15, 110, 1100, 110, 15, 7, 80}

输出

1210

解释

我们考虑子集 {15, 1100, 15, 80}，得到总和 1210，这是当子集中的两个元素不相邻时（以输入数组为参考）可以获得的最大和。

示例 2

输入

int inptArr[] = {3, 15, 11, 7, 180}

输出

195

解释

我们考虑子集 {15, 1100, 15, 80}，得到总和 1210，这是当子集中的两个元素不相邻时（以输入数组为参考）可以获得的最大和。

简单方法

对于这个问题，简单的办法是暴力法。在这个方法中，我们将找到给定输入数组的所有可能子集。在找到的子集中，我们将检查哪个是有效子集（对于这个问题，有效子集是指子集中任意两个元素都不相邻的子集）。对于有效子集，我们将计算总和，并根据找到的最大总和更新我们的答案。

文件名： MaxSumAdjEle.java

输出

For the input array: 
15 15 110 1100 110 15 7 80 
The Maximum Sum Such That No Two Elements Are Adjacent is: 1210


For the input array: 
3 15 11 7 180 
The Maximum Sum Such That No Two Elements Are Adjacent is: 195

复杂度分析：每次递归调用都会产生一次新的递归调用（一次不包含该元素，另一次包含该元素）。因此，程序的 time complexity 是指数级的。space complexity 是线性的，因为递归调用使用了栈。因此，程序的 time complexity 是 O(2ⁿ)。space complexity 是 O(n)，其中 n 是输入数组的总大小。

方法：使用动态规划

上述程序表明，每个元素都有两个选择。如果选择了该元素，则其相邻元素不能被选中。如果未选择该元素，则其相邻元素可以被选中，也可以不被选中。

因此，到第 j 个索引的最大和有两种可能性：一种是包含 inputArr[j] 的子序列，另一种是不包含 inputArr[j] 的子序列。

如果包含元素 inputArr[j]，则最大和取决于直到 (j - 1)^th 元素的子序列的最大和。显然，由于 inputArr[j] 已被包含，我们将排除 inputArr[j - 1] 元素。

如果排除元素 inputArr[j]，则最大和与直到 (j - 1) 的子序列的最大和相同，其中 inputArr[j - 1] 元素可以被包含或排除。

因此，我们需要构建一个 2-D 数组 dpArr[N][2]，其中 dp[i][0] 存储到第 j 个索引为止的最大子序列和（不包含 inputArr[i]），而 dpArr[j][1] 存储最大子序列和（包含 inputArr[i]）。

因此，我们得到动态规划方法中的以下关系。

dpArr[j][1] = dpArr[j - 1][0] + inputArr[j] 且 dpArr[j][0] = max(dpArr[j - 1][0], dpArr[j - 1][1])。

现在，请看实现解决方案所需的以下步骤。

步骤 1：如果数组大小为 1，则答案为 inputArr[0]。

步骤 2：初始化 dpArr[0][0] = 0 和 dpArr[0][1] = inputArr[0] 的值。

步骤 3：从 j = 1 迭代到 Siz - 1

• 根据上面所示的关系填充 dpArr[] 数组。

步骤 3：返回 dpArr[Siz - 1][1] 和 dpArr[Siz - 1][0] 之间的最大值。

观察下面的程序。

文件名： MaxSumAdjEle1.java

输出

For the input array: 
15 15 110 1100 110 15 7 80 
The Maximum Sum Such That No Two Elements Are Adjacent is: 1210


For the input array: 
3 15 11 7 180 
The Maximum Sum Such That No Two Elements Are Adjacent is: 195

复杂度分析：只需要一个循环来找到最大和。因此，程序的 time complexity 是 O(n)。此外，程序使用了一个包含输入元素数量两倍的数组。因此，程序的 space complexity 是 O(2 x n)，渐近表示为 O(n)，其中 n 是输入数组中元素的总数。

空间优化方法

如果我们查看上面的程序，我们会发现第 j 个元素的当前状态仅取决于最后一个遇到的元素的两个状态。因此，我们不必创建一个数组，而只需使用两个变量。

一个变量是 inclsv，它保存直到 j - 1 的子序列的最大和（当 inputArr[j - 1] 被包含时）。

另一个变量是 exclsv，它保存直到 j - 1 的子序列的最大和（当 inputArr[j - 1] 被排除时）。

图解

文件名： MaxSumAdjEle2.java

输出

For the input array: 
15 15 110 1100 110 15 7 80 
The Maximum Sum Such That No Two Elements Are Adjacent is: 1210


For the input array: 
3 15 11 7 180 
The Maximum Sum Such That No Two Elements Are Adjacent is: 195

复杂度分析：程序的 time complexity 与上一个程序相同，而程序的 space complexity 是 O(1)。