MaxNonAdjacentSum [最大非连接子集和]
# 介绍
给定一个由 N 个整数组成的数组 arr [] 和一个整数 K，任务是选择一些不相邻的数组元素，其最大和不超过 K。
最简单的方法是递归地生成给定数组的所有可能的子集，对于每个子集，检查它是否不包含相邻的元素，并且其总和不超过 K。在发现上述条件为真的所有子集中，打印任何子集获得的最大总和。
实现如下：
// Function to find the maximum sum not exceeding K possible by selecting a subset of non-adjacent elements
function maxSum(a, n, k) {
// Base Case
if (n <= 0) return 0;
// Not selecting current element
let option = maxSum(a, n - 1, k);
// If selecting current element is possible
if (k >= a[n - 1]) option = Math.max(option, a[n - 1] + maxSum(a, n - 2, k - a[n - 1]));
// Return answer
return option;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
时间复杂度：O (2N) 辅助空间：O (N)
为了优化上述方法，可以使用动态规划。每个数组元素都有两种可能的选择：跳过当前元素，进入下一个元素；只有当当前元素小于或等于 K 时才选择它。
按照下面的步骤来解决这个问题：
- 用 - 1 初始化一个数组
dp[N][K+1]，其中dp[i][j]将存储最大和，以利用索引 i 之前的元素求和 j。 - 从上述过渡中，如果当前元素被选中，找到最大和，如果没有被选中，则递归。
- 存储当前状态的最小答案。
- 同时，如果当前状态
(i，j)已经被访问，即dp[i][j]！=-1返回dp[i][j]。 - 打印
dp[N][K]作为最大和。
# 实现
# JavaScript
// Function find the maximum sum that doesn't exceeds K by choosing elements
function maxSum(a, n, k, dp) {
// Base Case
if (n <= 0) return 0;
// Return the memoized state
if (dp[n][k] != -1) return dp[n][k];
// Dont pick the current element
let option = maxSum(a, n - 1, k, dp);
// Pick the current element
if (k >= a[n - 1]) option = Math.max(option, a[n - 1] + maxSum(a, n - 2, k - a[n - 1], dp));
// Return and store the result
return dp[n][k] = option;
}
// Driver Code
// Given array
let arr = [ 50, 10, 20, 30, 40 ];
let N = arr.length;
let K = 100;
// Initialize dp
let dp = new Array(N + 1);
// Loop to create 2D array using 1D array
for (var i = 0; i < 1000; i++) dp[i] = new Array(2);
for (var i = 0; i < 1000; i++) for (var j = 0; j < 1000; j++) dp[i][j] = -1;
// Print answer
maxSum(arr, N, K, dp);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 扩展
求 nums 整数数组中的最大非相邻和。
/*
* Find the maximum non-adjacent sum of the integers in the nums input list
* :param nums: Array of Numbers
* :return: The maximum non-adjacent sum
*/
function maximumNonAdjacentSum (nums) {
if (nums.length < 0) return 0
let maxIncluding = nums[0]
let maxExcluding = 0
for (const num of nums.slice(1)) {
const temp = maxIncluding
maxIncluding = maxExcluding + num
maxExcluding = Math.max(temp, maxExcluding)
}
return Math.max(maxExcluding, maxIncluding)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 参考
编辑 (opens new window)
上次更新: 2022/10/25, 20:46:09