Reputation: 443
This isn't really a homework, but rather a practice and optimization, but this seemed like the best section for this type of questions.
It is a dynamical programming issue, and it's the following:
-Given an unsorted array of N elements, pick K number of elements from it, such that their absolute difference is the largest.
An absolute difference is calculated between adjacent elements here. So if we have an array of 5 elements: 1 5 3 2 1, and k = 3, the absolute differences would be:
1 5 3 = |5-1| + |3-5| = 6
1 5 2 = |5-1| + |2-5| = 7
1 5 1 = [5-1| + |1-5| = 8
etc
With 1 5 1 being the largest and needed one with 8
What i've tried so far is solving this by finding all possible combinations of K numbers with a recursion and then returning the biggest(brute force).
This showed as a terrible idea, because when tried with an array of N=50 and k=25 for example, there are 1.264106064E+14 combinations.
The recursion i used is a simple one used for printing all K-digit integers from an array, just instead of printing them, keeping them in an array:
static void solve(int[] numbers, int k, int startPosition, int[] result) {
if (k == 0) {
System.out.println(absoluteDifferenceSum(result));
return;
}
for (int i = startPosition; i <= numbers.length - k; i++) {
result[result.length - k] = numbers[i];
solve(numbers, k - 1, i + 1, result);
}
}
What I want to achieve is the optimal complexity (which i suppose can't be lower than O(n^2) here, but i'm out of ideas and don't know how to start. Any help is appreciated!
Upvotes: 1
Views: 1309
Reputation: 23955
Generally, we can have a naive O(n^2 * k)
formulation, where f(i, k)
represents the best result for selecting k
elements when the i
th element is rightmost in the selection,
f(i, k) = max(
f(j, k - 1) + abs(Ai - Aj)
)
for all j < i
which we can expand to
max( f(j, k - 1) + Ai - Aj )
= Ai + max(f(j, k - 1) - Aj)
when Ai >= Aj
and
max( f(j, k - 1) + Aj - Ai )
= -Ai + max(f(j, k - 1) + Aj)
when Ai < Aj
Since the right summand is independent of Ai
, we can build a tree with nodes that store both f(j, k - 1) - Aj
, as well as f(j, k - 1) + Aj
. Additionally, we'll store in each node both maxes for each subtree. We'll need O(k)
trees. Let's skip to the examination of the tree for k = 2
when we reach the last element:
1
5 -> 4 -> (-1, 9)
3 -> 2 -> (-1, 5)
2 -> 3 -> (-1, 5)
3 -> (-3, 5)
tree for k = 2 so far:
3 (-1, 5)
/ \
2 (-1, 5) 5 (-1, 9)
1 is less than 3 so we first add -1
to the max for the right subtree
stored for f(j, k - 1) + Aj
-1 + 9 = 8
(note that this represents {1,5,1})
then we continue left in the tree
and compare 8 to a similar calculation
with node 2: -1 + 5 = 4
(note that this represents {5,2,1})
This way, we can reduce the time complexity to O(n log n * k)
with space O(n * k)
.
Upvotes: 1