Author |
Topic: Find the largest sum from the set of +ve integers (Read 456 times) |
|
hary
Junior Member
Posts: 107
|
 |
Find the largest sum from the set of +ve integers
« on: May 15th, 2009, 6:08am » |
 Quote  Modify
|
Given a set 'S' of positive integers. Find the largest sum 'c' s.t. c = a+b where a,b,c belong to the Set 'S'.
|
|
 IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: Find the largest sum from the set of +ve integ
« Reply #1 on: May 21st, 2009, 10:09am » |
Quote Modify
|
strange to see no one responded on this thread so far.
Well one oif the solutions that i can think of the problem is
1. We know solution for the problem
Given an array (sorted) and a no 'X' and we can find out the pairs a,b that sum upto x in O(n) time.
Use this as the base solution where X will range from arr[n-1] to arr[2]. This solution has an O(n*n) complexity. What i am looking for is a more efficient solution if someone can come up with.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: Find the largest sum from the set of +ve integ
« Reply #2 on: May 21st, 2009, 10:13am » |
Quote Modify
|
This is related to the 3SUM problem, and doing better than O(n^2) is an open question.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print