### 题目描述补充 **题目：数组最大价值** 给定一个整数数组`arr`和一个整数`k`，你可以从中选择最多`k`个不相邻的元素。被选择的元素的和即为数组的最大价值。请编写一个函数来计算这个最大价值。 **示例 1**: ``` 输入: arr = [1, 3, 1, 15, 5, 2, 6], k = 3 输出: 23 解释: 选择索引为 1, 3 和 5 的元素，这些元素的和为 3 + 15 + 2 = 20。 但是，如果我们选择索引为 1, 3 和 4 的元素，和为 3 + 15 + 5 = 23，这是最大的。 ``` **示例 2**: ``` 输入: arr = [2, 4, 6, 2, 5], k = 2 输出: 11 解释: 选择索引为 1 和 4 的元素，和为 4 + 5 = 11。 ``` ### PHP 示例代码 ```php function maxSumAfterPartitioning($arr, $k) { $n = count($arr); if ($k >= $n) { return array_sum($arr); // 如果k大于等于数组长度，直接返回数组总和 } // dp[i][j] 表示在前i个元素中选择j个不相邻元素的最大价值 $dp = array_fill(0, $n + 1, array_fill(0, $k + 1, 0)); for ($i = 1; $i <= $n; $i++) { for ($j = 1; $j <= $k; $j++) { // 不选当前元素，继承前一个状态 $dp[$i][$j] = $dp[$i - 1][$j]; // 如果j > 0，可以选择当前元素（但需要跳过前一个元素） if ($i > 1) { $dp[$i][$j] = max($dp[$i][$j], $dp[$i - 2][$j - 1] + $arr[$i - 1]); } } } return $dp[$n][$k]; } // 测试代码 $arr = [1, 3, 1, 15, 5, 2, 6]; $k = 3; echo maxSumAfterPartitioning($arr, $k); // 输出 23 ``` ### Python 示例代码 ```python def maxSumAfterPartitioning(arr, k): n = len(arr) if k >= n: return sum(arr) # 如果k大于等于数组长度，直接返回数组总和 # dp[i][j] 表示在前i个元素中选择j个不相邻元素的最大价值 dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, k + 1): dp[i][j] = dp[i - 1][j] # 不选当前元素 if i > 1: dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + arr[i - 1]) # 如果j > 0，可以选择当前元素 return dp[n][k] # 测试代码 arr = [1, 3, 1, 15, 5, 2, 6] k = 3 print(maxSumAfterPartitioning(arr, k)) # 输出 23 ``` ### JavaScript 示例代码 ```javascript function maxSumAfterPartitioning(arr, k) { const n = arr.length; if (k >= n) { return arr.reduce((sum, val) => sum + val, 0); // 如果k大于等于数组长度，直接返回数组总和 } // dp[i][j] 表示在前i个元素中选择j个不相邻元素的最大价值 const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0)); for (let i = 1; i <= n; i++) { for (let j = 1; j <= k; j++) { dp[i][j] = dp[i - 1][j]; // 不选当前元素 if (i > 1) { dp[i][j] = Math.max(dp[i][j], dp[i - 2][j - 1] + arr[i - 1]); // 如果j > 0，可以选择当前元素 } } } return dp[n][k]; } // 测试代码 const arr = [1, 3, 1, 15, 5, 2, 6]; const k = 3; console.log(maxSumAfterPartitioning(arr, k)); // 输出 23 ``` **码小课网站中有更多相关内容分享给大家学习**，包括更多算法题解析、编程技巧等。