题目描述补充

题目：数组最大价值

给定一个整数数组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 示例代码

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 示例代码

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 示例代码

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

码小课网站中有更多相关内容分享给大家学习，包括更多算法题解析、编程技巧等。