largest sum

[electroRF]

Hi,

Given an unsorted list of N numbers, what is the the non-neighbored pair with the largest sum.

Example: {3, 45, 1, 5, 94, 100}, N = 6
Answer: (100,45)

Obviously, we can do it in O(N^2) - i.e. for each number in the array, go through all the numbers except for its neighbor, and update MAX_SUM if needed.

Is there a more efficient solution?

 

[BioniC187]

I'm sorry, could you please rewrite your method of calculating this?
I cannot make full sense of what you posted as the method

 

[NorthGuy]

Just select 3 largest numbers (you can do it in O(n)), then use the two of them which give the solution.

 

[electroRF]

NorthGuy,
A-W-E-S-O-M-E
Thank you.

B,
In the example I gave, 100 and 95 are the pair with the largest sum.
But 95 and 100 are neighbors so they can't form a pair according to the rules.

Therefore, 100 and 45 are the pair with the largest sum.

 

[electroRF]

Hi NorthGuy,

I'm wondering, how would you approach the problem if it was 'Given an unsorted list of N numbers, what is 5-number group with the largest sum, while having the group members non-neighbored'.

e.g. N = 15, list = {1, 5, 3, 10, 8, 9, 7, 3, 2, 4}
Result: 5, 10, 9, 3, 4

Would you take the largest 9 numbers (i.e. 5 numbers + 4 gaps) and from them consitute the 5-number group?

If it's true, it'd actually take (9*8*7*6*5 / 5! ) options to check for the desired group, right?

 

[NorthGuy]

Actually, I was wrong. To pick up 2 non-adjustent numbers you need not 3, but 4 largest numbers. If #1 is really big and #2 and #3 are adjactent to #1, then it may make sense to pick up (#1 and #4) over (#2 and #3).

To select more non-adjacent numbers, you will need more largest numbers, but I cannot tell you the formula on how many you could possibly need.

Once you get your group of the largest numbers, you don't need to go brute force, but can go intellegently about this - get the largest one and see what's around. Etc. etc.

If you want a full M numbers from array of N solution, it is rather complex and would require a through thinking to do it efficiently.

 

[electroRF]

Hi NorthGuy,

Actually, I was wrong. To pick up 2 non-adjustent numbers you need not 3, but 4 largest numbers. If #1 is really big and #2 and #3 are adjactent to #1, then it may make sense to pick up (#1 and #4) over (#2 and #3).

Great example, thanks you're right.


I found this method to get the max. sum of non-adjacent numbers.

Now i'm trying to figure out how u can change this problem a bit to make the group no larger than 5.

You think you can just first go over the entire array and find the largest group which sums up to the largest sum, and then remove the smallest numbers in this group to make it 5-number group?

 

[NorthGuy]

I don't thing this will give you a solution. They fund a sum of any quantity of non-ajacent numbers.

I would start from finding a solution for 1 number - very easy.

Then I would try to build an algorithm to find the solution for N+1 numbers when you already know the solution for N numbers. This is not very straightforward. As a beginning, I would define a set of "important" numbers - N ones already selected and all adjacent to them. Then I would find the biggest not important number and add it to the list of important numbers. Now I can get rid of all not important numbers - they are not going to be in my solution.

The set (numbers from previous solution and my newly added number) is a good candidate for the N+1 solution, but some permutatons may apply. You may need to replace some of the old numbers with the adjacent ones. E.g. you have ----4----786---- where 4 is your new number and 8 is from your previous solution. In this case you remove 8 and 4 and put in 7 and 6 instead. There must be a finite number of rules that you apply - needs a lot of thinking.

Why do you need all this suff? Looks useless