Chosing 1 out of multiple max elements

[Bilakos]

Hello i have a file with this numbers:

1 3 6 5 6

The code below finds the biggest numbers from left to right(->)and then prints how many of them were found(this is just a part of the whole code):

        int count = 0;
	for ( int i = 0, max = array[i]; i < array.size(); max = array[++i]) {
		for ( int a = i; a < array.size(); ++a)
			if (array[a] > max)
				max = array[i = a];
		++count;
	}
	cout << endl;
	cout << count << " found" << endl;

The problem is that when there is only 1 max element in my vector the program works right and says that it found 1 number but if there are 2 max elements(in this case 6 and 6)the program says it found 2 numbers.What i want to do,is tell it that if there are 2 or more max elements found,then choose the one that's closest to the end of the array,i was thinking about a for loop that would check from right to left(<-)to find the max element closest to the end.Sorry if i dont explain my problem very well,i dont know how else to say it.Thanks In Advance!

[dhayden]

You don't need two loops. Just make one pass and keep track of the max value, the number of times it occurred and the position in the array of the last occurrence:

    int max = numeric_limits<int>::min(); // requires #include <limits>
    size_t pos=0
    size_t count=0;

    for (int i=0; i<array.size(); ++i) {
        if (array[i] == max) {
            ++count;
            pos = i;
        } else if (array[i] > max) {
            count = 1;
            pos = i;
            max = array[i];
        }
    }

[Bilakos]

The same problem occurs when i try with your code,it still counts all max elements.I need the program to count only the max element closest to the end of the array(right),in case there are 2+ max elements.

[bugbyte]

Sorry, but after reading your question, the suggested solution and your reply, I don't understand what you want to achieve. I interpreted like dhayden did. Here's what you could do, to express your problem:

Give 3 sample inputs.
Give the matching output.

IMHO this is the goto way to explain a problem (of this type input -> do something ->output) if you have trouble precisely describing it wit words.

How I understood your problem:

Input:
1 3 6 5 6

Output:
closest max: 6 at index 4 (5th element)

[Bilakos]

I will explain my problem as much as I can.Think about the line with the numbers as a line of kids which are in a straight line,all looking at the same direction which is right(->).Each number represents the height of each kid.What I'm trying to do is to make a program that compares somehow these heights and outputs how many kids can see(at the right side).Here are some examples:

Input:
 1 3  6 5 6 4 2

Output:3

Explain:3 kids can see the right side,number 2 can see because it is first without any kids in front of it, number 4 can see too as it is taller than number 2 which is in front of it,number 6 can also see as it is taller from both 4 and 2.The rest of the kids behind the first 6(from right to left)won't be able to see as there is a taller kid in front of them all(the second six cannot see too as there is a kid with the same height in front of it).The problem here is that my program will output that 4 kids can see the right side as it counts both 6's.That's what I'm asking help for,how can I tell the program to count only the 6 that is closest the end of the vector that the heights are stored?(in this example the one that is behind number 4,position 4 of the vector)My current code gets confused when the tallest kids are 2 +( because they have the same height)I hope this explains my problem.

[DarkLightHitomi]

Okay, first, does "end" mean the last element or the first?

Second, do you want to show the element of the highest number or the position in line?

I'll give some pseudo code since I'm on my phone,

max;//array size
myarray;//the array
high;// highest number
highLoca;//location of highest number
highcount =0; //number of elements with the highest number

{//Code for entering the data in your array}

For (int iter =0; iter < max; iter++){ //iter++ will increase after each loop.
// Putting ++iter increases it before each loop which then skips element [0]

If (myarray[iter] > high) {
high = myarray[iter];
highLoca = iter; // this gives the element, for count just add 1
}// close if
}// close for loop

For (int iter =0; iter <0; iter++){
If (myarray[iter] == high) highcount++;
}//close for loop 2

Cout //whatever you want to display

If you want to show the left most highest element, reverse and go through the array from last element to first.

[m4ster r0shi]

I will explain my problem as much as I can.

This is what you should have done to begin with. See this and try to keep it in mind in your
future posts -> http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem

Now, assuming what you really want is 'the number of kids that can see to the right', it's possible
to do that in linear time (using a single for loop), but you'll have to traverse your array backwards:

#include <iostream>
#include <numeric>
#include <vector>

int main()
{
    std::vector<int> kidHeights = { 1, 3, 6, 5, 6, 4, 2, 3 };

    int numberOfKidsThatCanSeeToTheRight =
        std::accumulate(kidHeights.rbegin(), kidHeights.rend(), 0,
                        [](int curKidCount, int curHeight) {

                            // assuming positive heights
                            static int curMaxHeight = 0;

                            if (curHeight > curMaxHeight) {
                                ++ curKidCount;
                                curMaxHeight = curHeight;
                            }

                            return curKidCount;
                        });

    std::cout << numberOfKidsThatCanSeeToTheRight << std::endl;
}

http://ideone.com/Lq1YbQ

[Bilakos]

@m4ster r0shi

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> kidHeights = { 1, 3, 6, 5, 6, 4, 2, 3 };

    int numberOfKidsThatCanSeeToTheRight =
        std::accumulate(kidHeights.rbegin(), kidHeights.rend(), 0,
                        [&](int curKidCount, int curHeight) {

                            // assuming positive heights
                            static int curMaxHeight = 0;

                            if (curHeight > curMaxHeight) {
                                ++ curKidCount;
                                curMaxHeight = curHeight;
                            }

                            return curKidCount;
                        });

    std::cout << numberOfKidsThatCanSeeToTheRight << std::endl;
}

I tried to insert your code in my project but i get the error: accumulate was not declared in this scope at line 23
How can i fix this?Also yes thats what im trying to do,how many kids can the see to the right and if the code you gave me outputs 3 then its what im looking for.

[m4ster r0shi]

Sorry, my bad. You need to #include <numeric>. Fixed.

[Bilakos]

@m4ster r0shi
Still doesnt work,i think that the code you gave me is c++11 and im using an older one,this is a photo of the errors:
http://i.imgur.com/svOqVfI.png
And Here is my code in case this helps:

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main(){
    string kids;
    int y , x , pos;
    vector<int> array;
    ifstream input;
    ofstream output;
    input.open("input.in");
    output.open("output.out");
    getline(input,kids);
    cout << "The Number Of Kids Is " << kids << endl;
    istringstream buffer(kids);
    buffer >> y;
    for ( int i = 0 ; i < y ; ++i ) {
        input >> x;
        array.push_back(x);
    }
    for ( int i = 0;i < array.size(); ++i){
        cout << array[i] << " ";
    }
    int numberOfKidsThatCanSeeToTheRight =
            accumulate(array.rbegin(), array.rend(), 0,
                        [&](int curKidCount, int curHeight) {

                            // assuming positive heights
                            static int curMaxHeight = 0;

                            if (curHeight > curMaxHeight) {
                                ++ curKidCount;
                                curMaxHeight = curHeight;
                            }

                            return curKidCount;
                        });

    cout << numberOfKidsThatCanSeeToTheRight << endl;
    output << numberOfKidsThatCanSeeToTheRight;
    input.close();
    output.close();
    return 0;
}

Any suggestions?

[m4ster r0shi]

Well, you can use -std=c++11, as your compiler suggests. If you're using Code::Blocks, go Project -> Build options -> Compiler settings -> Compiler Flags and check the appropriate box. The process should be similar in other IDEs.

[DarkLightHitomi]

This seems so much simpler to me,

#include <iostream>
using namespace std;

void main(){
const int max=8;//array size
	int myarray[max] = { 1, 3, 6, 5, 6, 4, 2, 3 };//the array
	int high=0;// highest number
	int highLoca =0;//location of highest number
	int highcount = 0; //number of elements with the highest number

	for (int iter = 0; iter < max; iter++){
			if(myarray[iter] > high) {
				high = myarray[iter];
				highLoca = iter+1;
			}// close if
		}// close for loop

		for(int iter = 0; iter <0; iter++){
			if(myarray[iter] == high) highcount++;
		}//close for loop 2

		cout << "Highest kid is " << high << " high and number " << highLoca <<" in line.\n"<< endl;
}//close main 

[m4ster r0shi]

This seems so much simpler to me

There is an even simpler way to do what you did:

#include <algorithm>
#include <iostream>

int main()
{
    const int heightCount = 8;
    int kidHeights[heightCount] = { 1, 3, 6, 5, 6, 4, 2, 3 };

    // your first for loop
    auto maxHeightIter = std::max_element(kidHeights, kidHeights + heightCount);

    // your second for loop
    auto maxHeightCount = std::count(kidHeights, kidHeights + heightCount, *maxHeightIter);

    std::cout
        << "Highest kid is " << *maxHeightIter
        << " unit(s) high and number " << maxHeightIter - kidHeights + 1
        << " in line.\nThere are " << maxHeightCount
        << " kids with this height, in total." << std::endl;
}

http://ideone.com/SiEsMd

However, this is not what the OP wants to do. Read his 3rd post carefully and try again.
Perhaps reading my suggested solution and how std::accumulate works could help too.

Useful link -> http://www.cplusplus.com/reference/numeric/accumulate/

[DarkLightHitomi]

Other then format (and forgetting to include the highCount in cout, despite being calculated, oops, though now I see how to do it with a single for loop and be even simpler), what exactly does your code do that mine doesn't?

As far as I can tell, accumulate just adds a bunch of numbers together, and that isn't the goal. The closest we get is counting the number of kids with the highest height, but even that is secondary as the stated goal is to identify which element, of all those with the highest height, is the farthest to the right.

I'm not sure I'd consider including a bunch of other files and making function calls would be simpler, perhaps easier on the front end though.

[m4ster r0shi]

Okay, let's take things one step at a time. The first thing you need to do is realize that your code
does not solve the OP's real problem. Read the OP's 3rd post to see what he really wants to do.

[DarkLightHitomi]

Clearly we don't see the same thing from the same text.

My understanding...

...is that he needs to identify a single element, he implies that it needs to be the highest in normal use, but he has problems when there is a tie, thus he needs to identify a single element from all the highest elements. This is the key issue. Once identified, everything else is simple, whther you wish to know the element, the number of spaces from either side, or anything else all relies on identifying that single key element.

Further, he already has working code for what he wants when there is a single highest element, so all he really needs to know is how to modify it so when multiple elements are the highest, to pick only one element to do whatever he needs to do with it.

Calling them kids is simply trappings.

[m4ster r0shi]

My understanding...

...is that he needs to identify a single element, he implies that it needs to be the highest in normal use, but he has problems when there is a tie, thus he needs to identify a single element from all the highest elements. This is the key issue. Once identified, everything else is simple, whther you wish to know the element, the number of spaces from either side, or anything else all relies on identifying that single key element.

Well, then your understanding is not correct.

[DarkLightHitomi]

How do you know you are correct? Either or both of us could be wrong.

Besides, it isn't very helpful to tell me I'm wrong without the giving the details of what I'm missing, or why I'm wrong. (Notice how I told what I believe and why, rather than simply state my self righteousness.)

[m4ster r0shi]

it isn't very helpful to tell me I'm wrong without the giving the details of what I'm missing, or why I'm wrong.

But I have pointed you to the details. And not just one time, but twice.
Actually, let's make that three times: Read the OP's third post carefully.

Perhaps a couple of examples could help more:

Input:
6 6 5 4 3 2 1

Output: 6

Input:
6 6 1 2 3 4 5

Output: 2

Input:
6 6 4 5 2 3 1

Output: 4

Notice that the output is different even though the positions of the max elements do not
change. Having trouble understanding why? Let's visualize the inputs using kid heights:

Input:
* * 
* * * 
* * * *
* * * * *
* * * * * *
* * * * * * *
0 1 2 3 4 5 6

Output: 6

Here, kids 1 - 6 can see to their right, however kid 0 can't; its sight is blocked by kid 1.

Input:
* * 
* *         * 
* *       * *
* *     * * *
* *   * * * *
* * * * * * *
0 1 2 3 4 5 6

Output: 2

Only kids 1 and 6 can see to their right here; kid 0 is blocked by kid 1 and kids 2 - 5 are blocked by kid 6.

Input:
* * 
* *   *     
* * * *     
* * * *   * 
* * * * * * 
* * * * * * *
0 1 2 3 4 5 6

Output: 4

Kid 0 is blocked by kid 1, kid 2 by kid 3 and kid 4 by kid 5. The rest of them can see to their right.

PS: It just occurred to me that I may have had an unfair advantage in interpreting the OP's words this whole time. The OP's use of English suggests that he is a native Greek speaker, and I am one too. That said, I don't think it made that much of a difference.

[DarkLightHitomi]

In general, if someone is trying multiple descriptions of the same thing, but the descriptions appear different, the most common reason is a difference of perspective which is solved by examining all descriptions for the commonalities and not any single one. In any case I thought it was a poorly worded descriptive metaphor. Though it seems to have been edited (I had been reading the copy I made) to be bit clearer.

Though a lingual difference can indeed make things harder so I'll just take your word on the effects of that as I don't know greek.

I find your examples well presented, hopefuly it helps readers in their own attempts to describe problems.

Still thinking on it though, perhaps a recursive function, scope issues though I hate those. (Maybe I'll write a programming language that can join scopes.)