1. Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.
    Dismiss Notice

largest sum

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

  1. electroRF

    electroRF Member

    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
    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?
     
  2. BioniC187

    BioniC187 Member

    Joined:
    Aug 9, 2011
    Messages:
    281
    Likes:
    10
    I'm sorry, could you please rewrite your method of calculating this?
    I cannot make full sense of what you posted as the method
     
  3. NorthGuy

    NorthGuy Well-Known Member

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

    Dave New Member

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


     
  5. electroRF

    electroRF Member

    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. electroRF

    electroRF Member

    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. NorthGuy

    NorthGuy Well-Known Member

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

    electroRF Member

    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?
     
  9. NorthGuy

    NorthGuy Well-Known Member

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

Share This Page