一个小算法题：如何挑选总和最大的若干个数字？

无名啊

@Ta 05-05 22:21发布，05-05 22:29修改 80点击

描述

有一个长为 L 正整数数组 nums，请你从中找出 N 个数字，使得总和最大。（L <= 100w、N <= 1w）

注意：挑选出的任意两个数 nums[i]、nums[j]，需满足 a <= | i - j | <= b（其中，0 < a < b < L）。

背景

svt-av1 转码不支持场景变化检测，只能固定 x 秒插入一个关键帧，容易导致：

体积膨胀（不合时宜地插入太多冗余关键帧）
码率低时，关键帧前后内容有时突变（好比时不时从 720p 切换到 1080p，那一瞬间看着不舒服）

现发现 svt-av1 支持通过 --force-key-frames 自定义哪一帧是关键帧，再通过 ffmpeg -filter:v "select='gte(scene,0)',showinfo" 输出每一帧与前一帧场景变化程度，最后找前 N 大数值，可大体解决问题。

但不加限制地随意挑选关键帧，会导致：

关键帧设太频繁，体积膨胀太快。且这么短时间内，眼睛看不过来，没必要每一帧都高质量。所以最好至少 a 帧才能设一关键帧
太久不设关键帧，进度条拖拽不方便（比如只能跳转到 00:01:00、00:02:00……，想看个 00:01:50 还得等 50 秒），且距离关键帧远的地方质量逐渐变差。所以最好至多 b 帧要设一关键帧

隐藏样式查看源码

回复列表(2|隐藏机器人聊天)

1

水木易安

@Ta / 05-07 10:02 / 样 / 源
这个问题可以通过动态规划来解决。我们需要找出一个算法，在满足给定的约束条件下，从数组中选择 N 个数字，使得它们的总和最大。

假设数组为 nums，长度为 L，我们需要选择 N 个数字，且任意两个选定数字的索引差满足 a <= |i - j| <= b。

我们可以使用动态规划来解决这个问题。定义 dp[i][n] 表示从数组的前 i 个数字中选出 n 个数字的最大总和。在计算 dp[i][n] 时，我们需要考虑选或不选 i 位置的数字：
1. 如果不选 i 位置的数字，那么 dp[i][n] = dp[i-1][n]。
2. 如果选 i 位置的数字，那么我们需要从 i-a 到 i-b 的范围中选出 n-1 个数字的最大总和，这样 dp[i][n] = nums[i] + max(dp[j][n-1])，其中 i-b <= j <= i-a。
边界条件：
- dp[i][0] = 0，表示不选任何数字，总和为 0。
- dp[0][n] = nums[0]，如果 n = 1，否则为负无穷。
最终结果为 max(dp[L-1][N])。

伪代码如下：
```
def max_sum(nums, L, N, a, b):
    dp = [[-float('inf')] * (N + 1) for _ in range(L)]
    dp[0][1] = nums[0]

    for i in range(1, L):
        dp[i][0] = 0  # 不选任何数字，总和为 0
        for n in range(1, N + 1):
            dp[i][n] = dp[i-1][n]  # 不选 i 位置的数字
            if n == 1:
                dp[i][n] = max(dp[i][n], nums[i])  # 如果选择一个数字
            else:
                # 选 i 位置的数字
                for j in range(max(0, i-b), i-a+1):
                    dp[i][n] = max(dp[i][n], dp[j][n-1] + nums[i])

    return max(dp[L-1][N])

# 示例调用
nums = [1, 5, 2, 9, 5, 1, 7]
L = len(nums)
N = 3
a = 1
b = 3
print(max_sum(nums, L, N, a, b))
```
这个算法的时间复杂度为 O(L * N * (b-a))，在给定的约束条件下是可行的。通过这种方式，我们可以找到满足条件的最大总和。
2

无名啊

@Ta / 05-07 14:42 / 样 / 源

@水木易安，也没法确认算法对不对。。感觉得去补补动态规划。。

添加新回复

回复需要登录。