Given 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 positive integers, which I will denote as a0, a1, …, an-1. We are also given an integer k, and our task is to:

  1. find a subsequence of length exactly k (denoted as b0, b1, …, bk-1), such that abs(b1 - b0) + abs(b2 - b1) + … + abs(bk-1 - bk-2) is maximal; and

  2. output the sum (no need to output the entire subsequence).

I have been trying to solve this using a dynamic programming approach but all my efforts have been futile.

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

Example input:

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 help / hints would be greatly appreciated.


ANSWERS:


I managed to solve this problem. Here's the full 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 a friend of mine for hinting me at it). As mentioned in the comment, storage[i][j] keeps the optimal result where j + 1 elements are taken (K = j + 1) with numbers[i] appearing as the last element. Then, we simply try out each element appearing as the last one, taking each possible number of 1, 2, ..., K elements out of all. This solution works in O(k * n^2).

I first tried a 0-1 Knapsack approach where I kept the last element I had taken in each [i][j] index. This solution did not give a correct result in just a single test case, but it worked in O(k * n). I think I can see where it would yield a suboptimal solution, but if anyone is interested, I can post that code, too (it is rather messy though).

The code posted here passed on all test cases (if you can detect some possible errors, feel free to state them).



 MORE:


 ? Reducing time complexity in maximal minimum-sum 2-partitioning of an array
 ? Consecutve Subset Array Sum is a certain integer algorithm
 ? The English Tourist
 ? Calculate maximum profit under given path cost
 ? Given K sets of points, choose one point from each set such that the sum of pairwise distances between the selected points is minimized
 ? Distance between root and node in binary tree using recursion
 ? Check if Graph is Connected Upon Removal of Vertices
 ? How to find increasing subsequence of numbers with maximum sum?
 ? Finding the Longest Palindrome Subsequence with less memory
 ? How to find the actual sequence of a Longest Increasing Subsequence?