求解最大和递增子序列时,已算出最大和但无法回溯获取对应元素序列
现有回溯环节的核心缺陷
- 原代码的回溯判定仅通过
msis[i] < tempSeq[0]的数值大小关系筛选元素,缺失两个关键校验,导致序列选取错误:- 没有校验候选元素值是否小于当前已选序列的最右端元素,无法保证最终选出的序列符合递增要求
- 没有建立和值的匹配追踪机制,只是无差别纳入所有msis值更小的元素,遇到同msis值的干扰项就会定位到错误的前驱节点
- 比如原逻辑在处理示例输入时,遍历到索引1的70元素时,只要它的msis值小于当前待匹配的和值,就会被错误加入序列,直接破坏递增约束。
修正思路
- 回溯过程中维护两个状态变量,替代单纯的msis大小判断:
rightValue:当前已选序列最右端的元素值,作为下一个候选元素的大小上限,初始值为全局最大和对应的数组元素arr[maxIndex]requiredSum:当前需要匹配的前驱子序列的最大和值,初始值为全局最大和减去最右端元素的值,代表最右端元素前面的子序列需要凑出的和
- 从
maxIndex位置向前遍历数组,只有同时满足两个条件的元素才能被加入最终序列:- 候选元素的数组值小于当前
rightValue,符合递增子序列的大小要求 - 候选位置对应的msis最大和值,恰好等于当前的
requiredSum,证明这个位置就是当前序列的真实前驱节点
- 候选元素的数组值小于当前
- 每找到一个符合条件的元素,就同步更新两个状态值:把当前元素值更新为新的
rightValue,把当前位置的msis值减去自身元素值,作为下一轮需要匹配的新requiredSum,继续向前遍历直到走完所有数组元素。
修正后可直接运行的代码
const maxSubequence = (arr) => { let i, j; // 空数组边界处理 if (arr.length === 0) return [0, []]; let msis = arr.slice(); let maxSum = 0; let maxIndex = 0; let resultSeq = []; // 核心DP计算msis数组的逻辑本身无问题 for (i = 1; i < arr.length; i++) { for (j = 0; j < i; j++) { if (arr[i] > arr[j] && msis[i] < msis[j] + arr[i]) { msis[i] = msis[j] + arr[i]; } } } // 定位全局最大和的索引,这部分逻辑也无问题 for (i = 0; i < msis.length; i++) { if (maxSum < msis[i]) { maxSum = msis[i]; maxIndex = i; } } // 修正后的回溯取序列逻辑 let rightValue = arr[maxIndex]; let requiredSum = maxSum - rightValue; resultSeq = [rightValue]; for (i = maxIndex - 1; i >= 0; i--) { // 双条件校验:满足递增大小要求、匹配前驱的和值要求 if (arr[i] < rightValue && msis[i] === requiredSum) { resultSeq.unshift(arr[i]); rightValue = arr[i]; requiredSum = msis[i] - arr[i]; } } return [maxSum, resultSeq]; } console.log(maxSubequence([10, 70, 20, 30, 50, 11, 30])) // 控制台输出: [110, [10, 20, 30, 50]],和预期完全一致
内容的提问来源于stack exchange,提问作者חיים חדד
相关产品推荐
相关产品推荐

