最大连续数排序列表的算法

Question

我想在node js中编写一个遵循游戏规则的算法。它以一系列数字作为参数，并以第二个参数为休息前的最大连续天数（连续并不意味着值中连续，而是列表中位置连续），并且遵循以下逻辑： 我决定参加比赛来赢取金钱。

规则：

• 每天只有一场比赛
• 比赛是连续进行的
• 并非所有比赛都带来相同的金额
• 连续N场比赛
• 比赛总是从一号开始

我想通过参加所有可能的比赛来赢得尽可能多的胜利，只有在连续X场比赛之后我累了，我需要休息一天（在比赛中）。

程序需要显示最大增益：

示例：

共有10场比赛

您可以连续参加4场比赛

可能的支出为 13, 2, 15, 17, 19, 33, 2, 2, 2, 2。

因此您将玩以下日子：1 > 3 > 4 > 5 > 6 > 8 > 9 > * 10*

所以，您将赚取 103。

示例： [13, 12, 11, 9, 16, 17, 100]，最大比赛人数：3 => 169 [12, 14, 52, 7, 3, 1, 1, 89, 98, 100, 12, 5, 6, 8]，最大比赛人数：4 => 399

考虑到此列表中的示例： [5, 4, 1, 1, 1, 2, 3] 最多比赛次数为 2 我希望进行 5 > 4 > 休息 > 1 > 休息 > 2 > 3 或者在这个上： [5, 4, 1, 1, 2, 3] numberConsecutives: 2 我想做 5 > 4 > 休息 > 休息 > 2 > 3。 使增益最大化。如果有人可以提供帮助，那就太好了，提前致谢。

我正在使用 Typescript 进行开发并使用

ts-node

运行我的脚本。

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) {
      //possibilities.splice(possibilities.indexOf(possibilitie), 1);
      finalPossibilities.push(possibilitie);
    }
  });
  //console.log("possibilities", finalPossibilities);
  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

编辑

我已经尝试了很多方法来解决这个问题，但我认为我没有走正确的路，所以我正在寻找解决方案或一些建议来帮助我理解如何做到这一点。

[5, 4, 1, 1, 2, 3] numberConsecutives: 2

-> 我想做

5 > 4 > rest > rest > 2 > 3

。

为什么？

5 > 4 > 1 > 1 > 2 > 3

未获授权，因为我在没有休息日的情况下最多可以玩的次数是2。

5 > 4 > rest > 1 > 2 > rest

如果我那样去，我就被迫在最后一天休息，所以我失去了比 1 更好的 3。

这就是为什么

5 > 4 > rest > rest > 2 > 3

是最好的组合，因为它给了我

14

，这是我通过遵循规则可以达到的最佳数字。

Answer 1

这是一个通常需要动态规划方法的问题：跟踪到目前为止的最佳结果，区分当前连续序列的可能长度：因此对于每个可能的长度，跟踪迄今为止的最佳结果。这意味着记忆表将有

maxConsecutiveDays+1

条目，其中索引 0 反映使用休息日的情况。其他指数反映当前连续序列与该指数一样长。换句话说，我们并行考虑

maxConsecutiveDays+1

场景。最后我们可以选择最好的场景。

看起来是这样的：

function getMaxGains(numbers, maxConsecutiveDays) {
    const dp = Array(maxConsecutiveDays+1).fill(0);
    for (const value of numbers) {
        const max = Math.max(...dp);
        for (let i = maxConsecutiveDays; i > 0; i--) {
            dp[i] = dp[i-1] + value;
        }
        dp[0] = max;
    }
    return Math.max(...dp);
}

const tests = [
    [[13, 2, 15, 17, 19, 33, 2, 2, 2, 2], 4, 103],
    [[5, 4, 1, 1, 1, 2, 3], 2, 15],
    [[5, 4, 1, 1, 2, 3], 2, 14],
    [[13, 12, 11, 9, 16, 17, 100], 3, 169],
    [[12, 14, 52, 7, 3, 1, 1, 89, 98, 100, 12, 5, 6, 8], 4, 399]
];

for (const [numbers, maxConsecutiveDays, expected] of tests) {
    const result = getMaxGains(numbers, maxConsecutiveDays);
    console.log("got", result, "expected", expected);
}