# largest sum

Discussion in 'Mathematics and Physics' started by electroRF, Jan 16, 2014.

1. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal
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

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?

2. ### BioniC187Member

Joined:
Aug 9, 2011
Messages:
281
Likes:
10
I cannot make full sense of what you posted as the method

3. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
Just select 3 largest numbers (you can do it in O(n)), then use the two of them which give the solution.

• Like x 2

Joined:
Jan 12, 1997
Messages:
-
Likes:
0

5. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal

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.

6. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal
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?

7. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
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.

• Like x 1
8. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal
Hi NorthGuy,

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?

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location: