Largest number in subset

firehawk · 2008-03-27 12:04:05

Im not good at math, or even algorithms. I'm actually a software dev and just wondered if someone could give me an explanation and logic on how this is done.

say you are given an array of numbers. how do you find out the largest number in that subset? Example:

1, 2, 3, 4, -3, 8, 0, -20, 6

John E. Franklin · 2008-03-27 12:12:40

Assume the first number is the answer.
Then see if the next one is better.
If so, set answer = this next one.
Go to 3rd one.
Repeat till end of list.
Then answer variable will hold best one.

firehawk · 2008-03-27 12:16:19

John - are you sure? Because thats what I did and have a strong suspicion i have done this wrong. OK let me put it in some form of pseudo....

largeNumber = 0
total = 0

foreach number in arrayOfNumbers

total = total + number
if number > largeNumber then
largeNumber = number
end if

end foreach

for some reason I still think its wrong, it probably is. What IS a "subset" of a given set of numbers? What does that mean?

John E. Franklin · 2008-03-27 12:22:27

You're forgetting to set largeNumber to the first element in array
at the beginning.
Your code will return zero if all the numbers are negative numbers.

LuisRodg · 2008-03-27 12:24:36

Let A = {1,2,3,4,5} and let B = {1,2,3}

B is a subset of A.

When you say subset, you can think of it as "B is contained inside of A".

All the elements of B are also elements of A because B is a subset of A.

LuisRodg · 2008-03-27 12:30:36

Also for your original question.

Lets say you have an array of size n which contains integers and you want to see which element inside the array is the largest number.

------------------------------------------------------------

int max_num(int []array) {
int largest_n = array[0];

for (int i=0; i<array.length(), i++) {
if (array[i+1] > array[i])
largest_n = array[i+1];
}

return largest_n;
}

------------------------------------------------------------

Im rusty on my java/C++ so dont focus on the syntax.

This code assumes the first element in the array is the largest number and then loops through all the elements checking to see if the next one is larger than the previous, if it is then we assume it is the largest one and continue. When the iteration throughout all the elements in the array is done then largest_n will contain the largest number in the array.

Last edited by LuisRodg (2008-03-27 12:33:28)

JaneFairfax · 2008-03-27 12:33:58

For two numbers:

For more than three numbers

It should be possible from here to generalize to more than three numbers.

John E. Franklin · 2008-03-27 12:41:13

max{x,y,z} = (x + y + z)/3 +???? (This is a tough one, especially if they are not equally spaced apart)

mathsyperson · 2008-03-27 12:50:03

JaneFairfax wrote:

For two numbers:

But |z| = max{z,-z}, so you've got a circular definition there.
(Unless you piecewisely define the abs function piecewise, in which case you might as well piecewisely define max directly)

John E. Franklin · 2008-03-27 12:54:08

fix Luis's mistake:

for (int i=0; i<array.length() - 1 , i++) {

so you don't overrun end of array when accessing with the [i+1] > [i] thing.

Last edited by John E. Franklin (2008-03-27 12:55:41)

John E. Franklin · 2008-03-27 13:01:24

Last edited by John E. Franklin (2008-03-27 13:03:55)

JaneFairfax · 2008-03-27 13:02:13

mathsyperson wrote:

But |z| = max{z,-z}, so you've got a circular definition there.

|x| is defined as

max{x,y} is as stated above.

Now tell me where the f*** is the circularity?

John E. Franklin · 2008-03-27 13:12:57

firehawk · 2008-03-27 19:31:22

uh thanks folks, sorry i dont understand or know what this whole formula thing is (the whole max { w, x, y, z}.....

thanks for the code, yes I follow it and you are right I DID miss setting the largeNumber to the first element in the array.

drats. ok.... so basically you should be checking the NEXT number in the array to see if it is larger than the stored number in a temp variable. - but there is no point in doing that in your code since your kind of doubling the check....

foreach item in array

if currentitem + 1 in array > storedNumber

.. do stuff

end if

it is the same as:

for each item in array
if current item > storedNumber

//do stuff

end if

with the last example being more effecient....but anyway thats a coding thing.

just still not sure about the whole B is a subset of A...C is a subset of B (and A?)

LuisRodg · 2008-03-27 23:49:22

Thanks Franklin for fixing my code. It would have given an out of bound error.

Let A = {1,2,3,4,5} and let B = {1,2,3} and let C = {1,2}

the numbers inside the { } denote the elements contained in the set separated by commas.

Here B is a subset of A and C is a subset of B but since B is a subset of A then any subsets of B will logically be a subset of A as well.

this is called Set Theory and its not hard to understand. If you want to understand it better you might want to read on it. Post if you have any questions.

I think its really funny how we all ignored Jane's explosion on what I thought was a plausible mistake by mathsy...

mathsyperson · 2008-03-27 23:57:58

JaneFairfax wrote:

mathsyperson wrote:
But |z| = max{z,-z}, so you've got a circular definition there.

|x| is defined as
max{x,y} is as stated above.
Now tell me where the f*** is the circularity?

Fair enough, with that definition there's no circularity. I thought the other one was more common.

However, as I mentioned in the brackets, what you've effectively got there is:

You're using a piecewise definition anyway, so surely it would be better to just say:

Your way is a perfectly correct definition, it just seemed overly complicated.

firehawk · 2008-03-28 00:29:56

Thanks folks. much appreciated. Just need to try and understand all this for general purposes...you never know when you will get a question like that....and I did and messed it up bad!

so your saying that if we have:

1, 2, 3, 4, 5

we can have subsets:

1 = 1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15

I think i follow your Set Theory example....

so given the numbers in this reply, what would be the largest number in the subset?

LuisRodg · 2008-03-28 02:09:23

A set is a group or collection of elements. It can be numbers, persons, objects. Anything. It doesnt imply addition like you did. Sure, you could add the elements if its possible but that has nothing to do with the set itself.

A = {1,2,3,4,5}

B = {1,2,3} is a subset of the set above. We say its a subset because every single element in B is in A also. We dont care what those elements add up to.

To put an example that doesnt have to do with numbers so you dont think addition:

Let A = the set of all people living in the world.

Let B = the set of all people living in the US.

B is a subset of A because all the people living in the US also are part of the world. In other words, set B is contained inside set A, therefore B is a subset of A.

mathsyperson · 2008-03-28 02:13:12

Also, you don't have to restrict subsets to being the first elements of the set.

In your example with the set {1,2,3,4,5}, another valid subset could be {1, 2, 4}.

firehawk · 2008-03-28 02:18:22

gotcha...thanks for that

so again back to my question, how would you find the largest number in a subset? or the largest number within A subset

LuisRodg · 2008-03-28 02:27:10

Didnt we already help you with that?

firehawk · 2008-03-28 02:29:04

hmmm. so given this:

1, 2, 3, 4, 5

largest subset would be...all of it?

LuisRodg · 2008-03-28 02:38:28

What do you mean largest subset?

How do you define largest? By the amount of elements contained? In that case, that is called the cardinality of a set, denoted:

|A| = the amount of elements inside a set.

So given a set, the largest subset will be the same set itself. But I dont think this is the approach you want to get since it serves no purpose.

Could you tell us what are you using this on? What do you need to accomplish? If you need to find the largest element (given its a number) inside a set then just use the programming approach given above.

Please explain yourself.

JaneFairfax · 2008-03-28 02:59:12

firehawk · 2008-03-28 03:02:13

Thanks

im not trying to apply it on anything, its just a question that was given to me and just want to know the answer to it and how you would go about coming to that conclusion - its just mind boggling

Math Is Fun Forum

#1 2008-03-27 12:04:05

Largest number in subset

#2 2008-03-27 12:12:40

Re: Largest number in subset

#3 2008-03-27 12:16:19

Re: Largest number in subset

#4 2008-03-27 12:22:27

Re: Largest number in subset

#5 2008-03-27 12:24:36

Re: Largest number in subset

#6 2008-03-27 12:30:36

Re: Largest number in subset

#7 2008-03-27 12:33:58

Re: Largest number in subset

#8 2008-03-27 12:41:13

Re: Largest number in subset

#9 2008-03-27 12:50:03

Re: Largest number in subset

#10 2008-03-27 12:54:08

Re: Largest number in subset

#11 2008-03-27 13:01:24

Re: Largest number in subset

#12 2008-03-27 13:02:13

Re: Largest number in subset

#13 2008-03-27 13:12:57

Re: Largest number in subset

#14 2008-03-27 19:31:22

Re: Largest number in subset

#15 2008-03-27 23:49:22

Re: Largest number in subset

#16 2008-03-27 23:57:58

Re: Largest number in subset

#17 2008-03-28 00:29:56

Re: Largest number in subset

#18 2008-03-28 02:09:23

Re: Largest number in subset

#19 2008-03-28 02:13:12

Re: Largest number in subset

#20 2008-03-28 02:18:22

Re: Largest number in subset

#21 2008-03-28 02:27:10

Re: Largest number in subset

#22 2008-03-28 02:29:04

Re: Largest number in subset

#23 2008-03-28 02:38:28

Re: Largest number in subset

#24 2008-03-28 02:59:12

Re: Largest number in subset

#25 2008-03-28 03:02:13

Re: Largest number in subset

Board footer