For a sequence of n positive integers, find a subsequence of length k such that the sum over the absolute values ​​of the differences is maximal

We are given a sequence of n natural numbers, which I will denote as 0, a 1, ..., a n-1... We are also assigned an integer k, and our task is as follows:

  • find a subsequence of length exactly k (denoted as b 0, b 1, ..., b k-1), so that abs (b 1 - b 0) + abs (b 2 - b 1) + ... + abs (b k-1 - b k-2) is maximum; and

  • display the amount (there is no need to display the entire subsequence).

I am trying to solve this problem with a dynamic programming approach, but all my efforts have been in vain.

EDIT: k <= n. The elements in sequence b must appear in the same order they appear in (otherwise this could be solved simply by finding max, min, ... or min, max, ...).

Input example:

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

      

Output:

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

      

Any hints / tips are greatly appreciated.

+3


source to share


1 answer


I managed to solve this problem. Here's the complete code:

#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;
}

      

The idea is simple (thanks to my friend for giving me a hint). As mentioned in the comment, storage [i] [j] preserves the optimal result when j + 1 elements are accepted (K = j + 1), with the numbers [i] appearing as the last element. Then we just try each element that appears as the last one, taking every possible number of elements 1, 2, ..., K from all. This solution works in O (k * n ^ 2).



I first tried using the Knapsack 0-1 method where I saved the last item I used at each index [i] [j]. This solution did not give the correct result in only one test case, but worked in O (k * n). I think I can see where this will give a suboptimal solution, but if anyone is interested, I can post this code too (it's pretty messy).

The code shown here passed in all test cases (if you can find some possible errors, feel free to point them out).

+1


source







All Articles