正数数组中和≤k的最长子序列长度求解（不可排序，DP方案）

问题分析 #

我们需要在给定正整数数组中找到最长的非连续子序列（必须保持原元素顺序），满足子序列元素和≤给定值k。暴力枚举所有2ⁿ种情况效率极低，而排序后贪心的方法会破坏原顺序，因此采用动态规划（0-1背包变种）来解决。

DP状态定义 #

定义一维数组dp，其中dp[s]表示元素和恰好为s时，能得到的最长子序列长度。

• 初始状态：dp[0] = 0（和为0时，子序列长度为0），其余dp[s] = -∞（表示该和无法达到）。

状态转移 #

遍历数组中的每个元素num，从后往前（避免重复选取同一元素）更新dp数组：
对于每个s从k递减到num：

dp[s] = max(dp[s], dp[s - num] + 1)

• 解释：对于当前元素num，如果我们选择它，那么和为s的最长子序列长度，等于和为s - num的最长子序列长度加1；如果不选它，则保持dp[s]原有值。取两者的最大值。

计算结果 #

遍历dp[0...k]，找到其中的最大值，即为所求的最长子序列长度。如果所有值都是-∞（除了dp[0]），说明没有符合条件的非空子序列，返回0。

示例演示 #

假设数组为[3,1,4,2]，k=5：

1. 初始化dp = [0, -∞, -∞, -∞, -∞, -∞]
2. 处理元素3：
   • s从5到3：dp[3] = max(-∞, dp[0]+1) = 1
   • 此时dp = [0, -∞, -∞, 1, -∞, -∞]
3. 处理元素1：
   • s=5：dp[5] = max(-∞, dp[4]+1) = -∞
   • s=4：dp[4] = max(-∞, dp[3]+1) = 2
   • s=1：dp[1] = max(-∞, dp[0]+1) = 1
   • 此时dp = [0, 1, -∞, 1, 2, -∞]
4. 处理元素4：
   • s=5：dp[5] = max(-∞, dp[1]+1) = 2
   • s=4：dp[4] = max(2, dp[0]+1) = 2
   • 此时dp = [0, 1, -∞, 1, 2, 2]
5. 处理元素2：
   • s=5：dp[5] = max(2, dp[3]+1) = 2
   • s=4：dp[4] = max(2, dp[2]+1) = 2
   • s=3：dp[3] = max(1, dp[1]+1) = 2
   • s=2：dp[2] = max(-∞, dp[0]+1) = 1
   • 此时dp = [0, 1, 1, 2, 2, 2]
6. 遍历dp[0...5]，最大值为2，即最长子序列长度为2（例如[3,1]、[1,2]等）。

复杂度分析 #

• 时间复杂度：O(n*k)，其中n是数组长度，k是给定的和上限。符合题目要求的可接受复杂度。
• 空间复杂度：O(k)，使用一维数组存储状态，可直接优化至此。

边界情况处理 #

• 若k=0：由于数组元素都是正整数，无法选出任何元素，返回0。
• 若所有元素都大于k：同样无法选出非空子序列，返回0。

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