You need to enable JavaScript to run this app. 求解最大和递增子序列时,已算出最大和但无法回溯获取对应元素序列
优惠活动
大模型
产品
解决方案
定价
更多

求解最大和递增子序列时,已算出最大和但无法回溯获取对应元素序列

现有回溯环节的核心缺陷
  • 原代码的回溯判定仅通过msis[i] < tempSeq[0]的数值大小关系筛选元素,缺失两个关键校验,导致序列选取错误:
    1. 没有校验候选元素值是否小于当前已选序列的最右端元素,无法保证最终选出的序列符合递增要求
    2. 没有建立和值的匹配追踪机制,只是无差别纳入所有msis值更小的元素,遇到同msis值的干扰项就会定位到错误的前驱节点
  • 比如原逻辑在处理示例输入时,遍历到索引1的70元素时,只要它的msis值小于当前待匹配的和值,就会被错误加入序列,直接破坏递增约束。
修正思路
  • 回溯过程中维护两个状态变量,替代单纯的msis大小判断:
    1. rightValue:当前已选序列最右端的元素值,作为下一个候选元素的大小上限,初始值为全局最大和对应的数组元素arr[maxIndex]
    2. 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,提问作者חיים חדד

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.18 21:15:09