递归计算数组任意k个非连续元素最大和的最优算法及方案改进建议

架构老林

2026-5-9

求解数组中k个非连续元素的最大和

首先，咱们先明确问题核心：要从数组中选出k个互不相邻的元素，使得它们的和最大。你之前的递归代码没能得到正确结果，主要是因为没有把「选了多少个元素（k）」这个关键状态纳入递归逻辑里，而且终止条件和状态转移也没覆盖全场景。

问题分析与最优解法思路

最快的解法是动态规划（DP），时间复杂度为O(nk)，空间可以优化到O(k)，这是目前能达到的最优复杂度——因为你必须遍历每个元素，同时跟踪选了0到k个元素的状态，没办法再简化了。

动态规划状态定义

我们定义dp[i][j]表示：前i个元素中，选出j个非连续元素的最大和（这里数组索引从0开始，i对应数组的前i个元素，即a[0]到a[i-1]）。

状态转移方程

对于第i个元素（也就是a[i-1]），有两种选择：

不选这个元素：那最大和就等于前i-1个元素选j个的最大和，即dp[i][j] = dp[i-1][j]
选这个元素：那前一个元素（i-1）就不能选，所以最大和等于前i-2个元素选j-1个的最大和加上当前元素的值，即dp[i][j] = dp[i-2][j-1] + a[i-1]

最终取这两种情况的最大值：
dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + a[i-1])

初始化条件

当j=0时（选0个元素），不管多少个元素，和都是0：dp[i][0] = 0 对所有i成立
当i<j时（元素数量少于要选的个数），不可能完成，所以设为极小值（比如-Infinity），表示无效状态
当j=1且i>=1时，dp[i][1] = max(dp[i-1][1], a[i-1])，也就是前i个元素中最大的单个元素

代码实现（Java）

基础二维DP版本

public static long maxNonContiguousSum(int[] a, int k) {
    int n = a.length;
    if (k == 0) return 0;
    if (k > (n + 1) / 2) return -1; // 不可能选k个非连续元素的情况，比如n=5最多选3个
    
    // 初始化DP表
    long[][] dp = new long[n+1][k+1];
    
    // 初始化j>=1且i<j的情况为极小值
    for (int j = 1; j <= k; j++) {
        for (int i = 0; i < j; i++) {
            dp[i][j] = Long.MIN_VALUE;
        }
    }
    
    // 填充DP表
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= Math.min(k, i); j++) {
            // 不选当前元素的情况
            long notTake = dp[i-1][j];
            // 选当前元素的情况，需要保证i-2 >=0且j-1 >=0
            long take = (i >= 2 && dp[i-2][j-1] != Long.MIN_VALUE) ? (dp[i-2][j-1] + a[i-1]) : Long.MIN_VALUE;
            dp[i][j] = Math.max(notTake, take);
        }
    }
    
    return dp[n][k];
}

测试你给的例子：a={1,3,2,5,0,10}，k=2，调用后返回15，和预期一致。

空间优化版本（O(k)空间）

因为dp[i][j]只依赖dp[i-1][j]和dp[i-2][j-1]，我们可以用两个一维数组来替代二维数组：

public static long maxNonContiguousSumOptimized(int[] a, int k) {
    int n = a.length;
    if (k == 0) return 0;
    if (k > (n + 1) / 2) return -1;
    
    // prevPrev代表dp[i-2][...]，prev代表dp[i-1][...]
    long[] prevPrev = new long[k+1];
    long[] prev = new long[k+1];
    
    // 初始化无效状态
    for (int j = 1; j <= k; j++) {
        prevPrev[j] = Long.MIN_VALUE;
        prev[j] = Long.MIN_VALUE;
    }
    prev[0] = 0;
    prevPrev[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        long[] curr = new long[k+1];
        curr[0] = 0;
        for (int j = 1; j <= Math.min(k, i); j++) {
            long notTake = prev[j];
            long take = (i >=2 && prevPrev[j-1] != Long.MIN_VALUE) ? (prevPrev[j-1] + a[i-1]) : Long.MIN_VALUE;
            curr[j] = Math.max(notTake, take);
        }
        prevPrev = prev;
        prev = curr;
    }
    
    return prev[k];
}

记忆化递归版本

如果你更倾向于递归写法，需要加入备忘录来避免重复计算，递归函数的状态要包含「当前处理到的索引」和「已经选了多少个元素」：

import java.util.HashMap;
import java.util.Map;

public class Solution {
    private Map<String, Long> memo;
    private int[] a;
    
    public long maxNonContiguousSumRecursive(int[] a, int k) {
        this.a = a;
        this.memo = new HashMap<>();
        long result = rec(a.length - 1, k);
        return result == Long.MIN_VALUE ? -1 : result;
    }
    
    private long rec(int idx, int remaining) {
        // 终止条件
        if (remaining == 0) return 0; // 选够了k个，和为0（加上之前选的）
        if (idx < 0) return Long.MIN_VALUE; // 元素不够了，返回极小值
        
        String key = idx + "," + remaining;
        if (memo.containsKey(key)) return memo.get(key);
        
        // 选当前元素：剩下的要从idx-2开始选，remaining减1
        long take = rec(idx - 2, remaining - 1);
        if (take != Long.MIN_VALUE) {
            take += a[idx];
        }
        
        // 不选当前元素：从idx-1开始选，remaining不变
        long notTake = rec(idx - 1, remaining);
        
        long max = Math.max(take, notTake);
        memo.put(key, max);
        return max;
    }
}

为什么你的递归代码不对？

你之前的递归函数没有跟踪「已经选了多少个元素」，而且参数n的含义不明确，状态转移也只考虑了选当前元素加之前的和，没有处理「不选当前元素」的情况，也没有终止条件判断是否选够了k个，所以无法得到正确结果。

内容的提问来源于stack exchange，提问作者L m