algorithm - 给定一个由 n 个正整数组成的序列，找到一个长度为 k 的子序列，使得差的绝对值之和最大

Question

我们有一个 n 个正整数序列，我将其表示为 a₀, a₁ , ..., a_n-1。我们还得到了一个整数 k，我们的任务是:

1. 找到长度恰好为 k 的子序列(表示为 b₀, b₁, …, b_k-1)，这样 abs(b₁ - b₀) + abs(b₂ - b₁) + … + abs(b_k-1 - b_k-2) 是最大的；和

2. 输出和(不需要输出整个子序列)。

我一直在尝试使用动态规划方法来解决这个问题，但我所有的努力都是徒劳的。

编辑: k <= n。序列 b 中的元素必须以与它们在 a 中出现的顺序相同的顺序出现(否则，这将通过简单地找到 max、min、... 或 min 来解决, 最大, ...).

示例输入:

n = 10
k = 3
1 9 2 3 6 1 3 2 1 3

输出:

16 (the subsequence is 1 9 1, and abs(9 - 1) + abs(1 - 9) = 8 + 8 = 16)

任何帮助/提示将不胜感激。

Answer 1

我设法解决了这个问题。这是完整的代码:

#include <stdio.h>
#include <stdlib.h>

int abs(int a)
{
    return (a < 0) ? -a : a;
}

int solve(int *numbers, int N, int K)
{
    int **storage = malloc(sizeof(int *) * N);
    int i, j, k;
    int result = 0;

    for (i = 0; i < N; ++i)
        *(storage + i) = calloc(K, sizeof(int));

    // storage[i][j] keeps the optimal result where j + 1 elements are taken (K = j + 1) with numbers[i] appearing as the last element.

    for (i = 1; i < N; ++i) {
        for (j = 1; j < K; ++j) {
            for (k = j - 1; k < i; ++k) {
                if (storage[i][j] < storage[k][j - 1] + abs(numbers[k] - numbers[i]))
                    storage[i][j] = storage[k][j - 1] + abs(numbers[k] - numbers[i]);

                if (j == K - 1 && result < storage[i][j])
                    result = storage[i][j];
            }
        }
    }

    for (i = 0; i < N; ++i)
        free(*(storage + i));

    free(storage);
    return result;
}

int main()
{
    int N, K;
    scanf("%d %d", &N, &K);
    int *numbers = malloc(sizeof(int) * N);
    int i;

    for (i = 0; i < N; ++i)
        scanf("%d", numbers + i);

    printf("%d\n", solve(numbers, N, K));

    return 0;
}

这个想法很简单(感谢我的一个 friend 向我暗示)。如评论中所述， storage[i][j] 保持最佳结果，其中 j + 1 个元素(K = j + 1)与 numbers[i] 作为最后一个元素出现。然后，我们简单地尝试每个元素作为最后一个出现，从所有元素中取出 1, 2, ..., K 个可能的元素。此解决方案适用于 O(k * n^2)。

我首先尝试了 0-1 Knapsack 方法，其中我保留了每个 [i][j] 索引中的最后一个元素。该解决方案仅在单个测试用例中没有给出正确的结果，但它在 O(k * n) 中起作用。我想我可以看到它会在哪里产生次优解决方案，但如果有人感兴趣，我也可以发布该代码(尽管它相当困惑)。

此处发布的代码通过了所有测试用例(如果您能检测到一些可能的错误，请随时指出)。