Link to home
Start Free TrialLog in
Avatar of KaranGupta
KaranGupta

asked on

query regarding a program

Hi

Given a list, array, of integers, find the index of the two consecutive numbers which have the

largest sum.For example, if the array is 1, 2, 3, 4, 5, the answer is 4 and 5, as 4+5 = 9.
Avatar of AndyAinscow
AndyAinscow
Flag of Switzerland image

OK - so what is your problem?  

Don't forget if this is homework then experts can't provide working code.
Also, is the array ordered, or is the order random?
Avatar of KaranGupta
KaranGupta

ASKER

Hi Cluskitt
It can be unordered.

AndyAinscow:

I am not giving any home work, Just give me some hint how should I go
SOLUTION
Avatar of AndyAinscow
AndyAinscow
Flag of Switzerland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Hi AndyAinscow

Ok noted. but I want to find the largest sum  where number are not consecutive like

int[] arr = {1,4,3,5,2} ;

then how can I do that. Please advice.
I thought you wanted the sum of the highest consecutive ones? Anyway, you can find either values easily with my approach. Order the array, then start at the top.
This is from the question:
find the index of the two consecutive numbers which have the largest sum

But then sorting (ordering) the array is bad - massive overhead.
Use Array.Sort

http://www.csharp-examples.net/sort-array/

to sort the array and take the last 2 values as specified by Cluskitt. but i donot think this is  correct answer as

your question says
"find the index of the two consecutive numbers which have the largest sum"

give some more examples
You can easily find the index as well. Simply duplicate the array into a two dimensional array, where the second dimension is the original index. Then you can find the highest value and check for the original index. It's still simpler that way, I believe.
For example, {1,4,3,5,2}  would end up like:
{1,2,3,4,5} {1,5,3,2,4}
When you would check for 5+4, it would tell you that their indexes would be 4 and 2, respectively.
Even worse now than just sorting I think.  More memory usage is now introduced !!!
Well, if memory becomes an issue, then this isn't the way to go. But, for this task, and for today's technology, the memory used is irrelevant. Even if you were to use an array of a thousand records, duplicating it and sorting it wouldn't take that much memory. And it would be a lot faster than looping through them all trying to find the two correct values.
So, it depends on what your more worried about: performance or memory allocation. Either way shouldn't have a relevant difference with today's computers.
And how can one sort the array without first looping through it ?  
There are array sorting functions built in in many languages, including C# and VB:Net which are the zones posted. To duplicate it you only need to loop once to write the original index (a basic arr(i)=i loop), after which you apply one of those sort functions and your work is mostly done.
Doing it without ordering would mean that you'd have to loop the entire array to find the highest two highest values, then again if those didn't satisfy the condition. And again, and again.
One approach values performance (speed), the other values resources (memory). Both are valid and depend on the rest of the application, criteria, etc...
You seem to be missing the point - the sort the array requires looping through it more than once (may not be integral number of times! - depends on the algorithm being used).  If you then duplicate the array as well per your later comment then that introduces yet more overhead.  (Mobile based apps may not be as free to use any amount of memory - so saying memory usage is irrelevant isn't a good idea).

Just because a modern PC has a lot of processor power and memory doesn't mean that gives one a licence to write poor code.
Not really. My suggestion doesn't need to loop the array except once to set the original index. After that, it applies the .Sort function which the .Net engine possesses. Once that is done, I don't need to loop the array. I just start at the top (which is the highest value) and check if the previous one is consecutive or not. If so, it's the answer, nothing else required. If not, I check the next index. I only loop the array if no values are consecutive.
Or, instead of creating a two dimension array, I can just duplicate with a normal one, sort it with the engine function, find the correct values and only loop the original array once to find the index. Either way, I only loop the array once. Once the engine has sorted the duplicated array, finding the correct answer is almost immediate.
Sorting an array involves a lot of processing.  To say you don't loop through the array because you delegate that to the system sort function is rubbish.
The system uses a lot less processing than looping because it keeps items indexed. It's similar to order by in an sql query. As long as the field is indexed, the system can easily handle it. Similarly, because of the way arrays are created, it's much simpler for the system to sort an array than for the user to loop/compare and sort it manually.
At no point did I suggest sorting in any way - you did.  I suggested looping through to find the items that fit the requirements.


ps.
I've made a small app - just calling the built in Sort function on the collection takes an order of magnitude longer than my complete routine (which I haven't even tried to optimise).