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.
source to share
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).
source to share