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

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).