I am given an array of integers. I need to find max sum of its elements so that any two elements are not neighbors. Example : sum(2, 5, 2) = 5 because we choose just 5; sum(3, 10, 2, 4, 10) = 20 because we choose 10 and 10; sum(10, 12, 5, 2) = 15 because we choose 10 and 5. How can it be done using any programming language? I have been working on this problem for several hours and the only thing I understand that it should use DP.
3
-
Correct its easy.. what's the question?SMA– SMA2016-01-23 13:55:21 +00:00Commented Jan 23, 2016 at 13:55
-
These lectures are getting more imaginative by the day for homework questions - so what have you tried?Ed Heal– Ed Heal2016-01-23 13:57:05 +00:00Commented Jan 23, 2016 at 13:57
-
I really like to see an answer for this question...i took a pencil and a piece of paper and worked this problem out for hours without result...so can anyone post an answer to this question instead of commenting useless things!Shrikantha Budya– Shrikantha Budya2016-01-24 04:09:13 +00:00Commented Jan 24, 2016 at 4:09
Add a comment
|
1 Answer
So I've implemented a solution in Java without using DP; I've simply used recursion. I'll try to explain it a bit.
First of all, we have to find a base case:
- if the array length is == 1, then sum(array) = array[0]
- besides, if the array length is == 2, then sum(array) = max(array[0],array[1])
Now, let's get to the general case of array.length = n. We have to decide whether or not array[n-1] is part of the solution; that is, if sum, launched on the first n-1 elements, is smaller than sum launched on the first n-2 elements + nth element of the array.
In a nutshell, we are saying "Is it better to consider the nth element or its neighbour (nth-1)?" Indeed, we cannot consider both, therefore we have to choose one.
private static int sum (int[] array) {
return aux (array,array.length);
}
private static int aux (int[] array, int upTo) {
if (upTo == 1)
return array[0];
else if (upTo == 2)
return (array[1] > array[0])
? array[1] : array[0];
else {
int tmpMax1 = aux (array,upTo-1);
int tmpMax2 = aux (array,upTo-2) + array[upTo-1];
return (tmpMax2 > tmpMax1)
? tmpMax2 : tmpMax1;
}
}
public static void main(String[] args) {
//just a bunch of simple tests. Too lazy to use JUnit
System.out.println(sum(new int[]{2}) + " = 2");
System.out.println(sum(new int[]{2, 5}) + " = 5");
System.out.println(sum(new int[]{2, 5, 2}) + " = 5");
System.out.println(sum(new int[]{3, 10, 2, 4, 10}) + " = 20");
System.out.println(sum(new int[]{10, 12, 5, 2}) + " = 15");
System.out.println(sum(new int[]{10, 12, 5, 2,100}) + " = 115");
System.out.println(sum(new int[]{10, 10, 10, 10,100}) + " = 120");
}
1 Comment
Rustam Ibragimov
Thank you very much! The explanation and the solution is just perfect