TypeScript实现符合规则的竞赛最大收益算法求助

需求说明 #

用TypeScript（ts-node运行）实现算法，参数为每日竞赛收益数字列表和最大连续参赛天数（指列表位置连续，非数值连续），需遵循规则：

• 每天仅一场竞赛
• 竞赛连续举办
• 各竞赛收益不同
• 共有N场连续竞赛
• 竞赛从第1天开始

算法目标是计算可获得的最大收益。

示例说明 #

• 输入列表[14,3,14,18,20,34,1,1,1,1]、最大连续天数4，最优选择为第1、3、4、5、6、8、9、10天参赛
• 输入列表[5,4,1,1,2,3]、最大连续天数2，最优选择为5>4>休息>休息>2>3，总收益14

现有问题 #

当前实现的getMaxGains函数结果不符合预期：

• Example1：输入[13,12,11,9,16,17,100]、maxConsecutiveDays=3，输出178，预期169
• Example2：输入[12,14,52,7,3,1,1,89,98,100,12,5,6,8]、maxConsecutiveDays=4，输出396，预期399

多次调整仍未解决，寻求解决方案或指导。

现有代码 #

function getMaxGains(numbers: any, maxConsecutiveDays: any) {
  function calculatePossibilitySum(possibility: any) {
    return possibility.reduce((acc: any, num: any) => acc + num, 0);
  }

  function generatePossibilities(numbers: any) {
    const possibilities = [];

    for (let i = 1; i <= numbers.length; i++) {
      for (let j = 0; j <= numbers.length - i; j++) {
        const possibility = numbers.slice(j, j + i);
        possibilities.push(possibility);
      }
    }

    return possibilities;
  }

  function sortPossibilities(possibilities: any) {
    return possibilities.sort(
      (a: any, b: any) =>
        calculatePossibilitySum(b) - calculatePossibilitySum(a)
    );
  }

  function findMaxGains(possibilities: any, maxConsecutiveDays: any) {
    let maxGains = 0;
    const selectedDays = new Set();

    for (const possibility of possibilities) {
      let consecutiveCount = 0;
      let canPlay = true;

      for (const day of possibility) {
        if (selectedDays.has(day)) {
          consecutiveCount = 0;
          canPlay = false;
          break;
        }
        console.log("day", day);
        consecutiveCount++;
        if (consecutiveCount > maxConsecutiveDays) {
          canPlay = false;
          break;
        }
      }

      if (canPlay) {
        console.log("possibility", possibility);
        maxGains += calculatePossibilitySum(possibility);
        possibility.forEach((day: any) => selectedDays.add(day));
      }
    }

    return maxGains;
  }
  const possibilities = generatePossibilities(numbers);
  const finalPossibilities: any = [];
  possibilities.forEach((possibilitie: any) => {
    if (possibilitie.length < maxConsecutiveDays + 1) {
      finalPossibilities.push(possibilitie);
    }
  });
  const sortedPossibilities = sortPossibilities(finalPossibilities);
  const maxGains = findMaxGains(sortedPossibilities, maxConsecutiveDays);

  return maxGains;
}

const example1 = [13, 12, 11, 9, 16, 17, 100];
const maxConsecutiveDays1 = 3;
const result1 = getMaxGains(example1, maxConsecutiveDays1);
console.log(result1); // Output: 178 expected: 169

const example2 = [12, 14, 52, 7, 3, 1, 1, 89, 98, 100, 12, 5, 6, 8];
const maxConsecutiveDays2 = 4;
const result2 = getMaxGains(example2, maxConsecutiveDays2);
console.log(result2); // Output: 396 expected: 399

问题分析与解决方案 #

现有代码核心问题 #

1. 日期跟踪错误：将收益值当作“天数”存入selectedDays，实际应跟踪日期的索引（如第0天、第1天），否则会误判不同日期但收益相同的情况。
2. 贪心逻辑错误：优先选择总和最大的连续子数组，这种局部最优会破坏全局最优。比如Example1中，代码会错误选择前4天（连续4天，超过maxConsecutiveDays=3的限制），导致收益计算违规。

正确思路：动态规划 #

通过动态规划跟踪两种核心状态：

• dp[i][0]：第i天不参赛时的最大收益
• dp[i][1][k]：第i天参赛，且已连续参赛k天（1<=k<=maxConsecutiveDays）时的最大收益

状态转移方程：

1. 第i天不参赛：dp[i][0] = max(dp[i-1][0], max(dp[i-1][1][1..maxConsecutiveDays]))
2. 第i天参赛且连续1天：dp[i][1][1] = dp[i-1][0] + numbers[i]
3. 第i天参赛且连续k>1天：dp[i][1][k] = dp[i-1][1][k-1] + numbers[i]

最终最大收益为最后一天所有状态的最大值。

修正后的代码 #

function getMaxGains(numbers: number[], maxConsecutiveDays: number): number {
    const n = numbers.length;
    if (n === 0) return 0;

    // dp0[i]：第i天不参赛的最大收益
    const dp0: number[] = new Array(n).fill(0);
    // dp1[k]：当前天参赛，连续参赛k天的最大收益（k从1到maxConsecutiveDays）
    const dp1: number[] = new Array(maxConsecutiveDays + 1).fill(-Infinity);

    // 初始化第0天
    dp0[0] = 0;
    dp1[1] = numbers[0];

    for (let i = 1; i < n; i++) {
        // 计算第i天不参赛的最大收益：取前一天所有状态的最大值
        const prevMax = Math.max(dp0[i-1], Math.max(...dp1.slice(1)));
        dp0[i] = prevMax;

        // 计算第i天参赛的状态
        const newDp1 = [...dp1];
        // 连续参赛1天：前一天不参赛 + 当前收益
        newDp1[1] = dp0[i-1] + numbers[i];
        // 连续参赛k天（k>1）：前一天连续k-1天 + 当前收益
        for (let k = 2; k <= maxConsecutiveDays; k++) {
            newDp1[k] = dp1[k-1] + numbers[i];
        }
        // 更新dp1状态
        newDp1.forEach((val, idx) => dp1[idx] = val);
    }

    // 最后一天的最大收益：不参赛或参赛任意连续天数的最大值
    return Math.max(dp0[n-1], Math.max(...dp1.slice(1)));
}

// 测试示例1
const example1 = [13,12,11,9,16,17,100];
const maxConsecutiveDays1 = 3;
console.log(getMaxGains(example1, maxConsecutiveDays1)); // 输出169，符合预期

// 测试示例2
const example2 = [12,14,52,7,3,1,1,89,98,100,12,5,6,8];
const maxConsecutiveDays2 = 4;
console.log(getMaxGains(example2, maxConsecutiveDays2)); // 输出399，符合预期

代码解释 #

1. 状态定义：用dp0记录每天不参赛的最大收益，dp1记录连续参赛k天的最大收益，简化了高维数组操作。
2. 初始化：第0天不参赛收益为0，连续参赛1天收益为当天数值，连续超过1天的收益设为负无穷（不可能发生）。
3. 状态转移：
   • 不参赛时，收益取前一天所有状态的最大值。
   • 参赛时，连续1天的收益来自前一天不参赛的情况；连续k天的收益来自前一天连续k-1天的情况。
4. 结果计算：取最后一天所有状态的最大值，即为全局最大收益。

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