C++ searching for biggest numbers in array

Question

I need to count the biggest number in array on the left and on the right from the actual index. I mean if my array is

1, 3, 2, 4, 3;

I need to output:

//Left Right
1 4 //no bigger on left, so 1; the biggest on right is 4
3 4 //and so on with rest points
3 4
4 4
4 3

I need to do this VERY fast, so just couting on left and then on right is a bad idea. I decided to just find the biggest on right, and then when I get there count the next one, and so on. With biggest on left, just if actual is bigger than it, change it. But something its not working... The program sometimes gives the wrong output. Unfortunately, I dont know on what input it does...

Here is my code, If you can see any general or algorithm errors Id be pleased if you can post it...

#include <cstdlib>
#include <iostream>

using namespace std;

inline int findmax(int tab[], int beg, int end)
{
    int max=0;
    for (int j=beg; j<end; j++)
        if (tab[j]>max) max=j;
    return max;
}

int main(int argc, char *argv[])
{

    int len;
    cin>>len;

    int h[len];
    for (int i=0; i<len; i++)
    cin>>h[i];

    int maxl=0, maxr;

    maxr=findmax(h,0,len);

    for (int i=0; i<len; i++)
    {
        if (h[i]>h[maxl]) maxl=i;
        if (i>maxr) maxr=findmax(h,i,len);
        cout<<h[maxl]<<" "<<h[maxr]<<endl;
    }
    //system("pause");
    return 0;
}

EDIT: I've read all replies and implemented it. The one problem is that I cant store the values in first loop, so i must "merge" the two for's... Here is my code for now:

#include <cstdlib>
#include <iostream>

using namespace std;

inline int findmax(int tab[], int beg, int end)
{
    int max=0;
    for (int j=beg; j<end; j++)
        if (tab[j]>max) max=j;
    return max;
}

int main(int argc, char *argv[])
{

    int len;
    cin>>len;

    int h[len];
    int l[len];
    for (int i=0; i<len; i++)
    cin>>h[i];

    int maxl=0, maxr;

    maxr=len-1;

    for (int i=len-1; i>=0; i--)
    {
        if (h[i]>h[maxr]) maxr=i;
        l[i]=h[maxr];
    }

    for (int i=0; i<len; i++)
    {
        if (h[i]>h[maxl]) maxl=i;
        cout<<h[maxl]<<" "<<l[i]<<endl;
    }
    //system("pause");
    return 0;
}

Answer 1

stefaanv (approximately) identified your issue, so I'll just show an implementation that's not O(n^2).

Edit: for minimum memory use

#include <iostream>
#include <array>
#include <algorithm>

int main()
{
    std::array<int,5> input = {1, 3, 2, 4, 3}; // max_right
    std::array<int,5> max_left;

    max_left[0] = input[0];
    for(int i=1;i<input.size();++i) {
        max_left[i] = std::max(max_left[i-1],input[i]);
    }

    for(int i=input.size()-2;i>=0;--i) {
        input[i] = std::max(input[i+1],input[i]);
    }

    for(int i=0;i<input.size();++i) {
        std::cout << max_left[i] << ' ' << input[i] << '\n';
    }
}

Answer 2

An improvement to the accepted answer:

You can eliminate at least 25% (possibly 50%) of the comparisons by going halfway.

Start from the left and compute the "left maximum" as you go. Start from the right and compute the "right maximum" as you go.

After meeting in the middle, compare the left maximum with the right maximum at the meeting point. If they're equal, then you know the answer for the rest of the computations (you've saved 50% of the calculations). If they're not equal, then you have to continue your calculations on the side that has the greater maximum of the two halves, up to the point where you reach the maximum on that side, and then you know the answer for the rest of that side.

Answer 3

Here's an implementation of what interjay is talking about:

#include <iostream>
#include <limits.h>

#define LENGTH 5
int h[LENGTH] = {1, 3, 2, 4, 3};
int maxl[LENGTH], maxr[LENGTH];

int main(int argc, char **argv)
{
    int max = INT_MIN;
    for(int i = 0; i < LENGTH; i++)
    {
        if (h[i] > max){ max = h[i]; }
        maxl[i] = max;
    }

    # Left to right, computer maxl
    max = INT_MIN;
    for(int i = LENGTH-1; i >= 0; i--)
    {
        if (h[i] > max){ max = h[i]; }
        maxr[i] = max;
    }

    # Right to left, computing maxr
    for (int i = 0; i < LENGTH; i++)
    {
        std::cout << maxl[i] << " " << maxr[i] << std::endl;
    }
    return 0;
}

It sounds like you're limited on memory. In that case, you can get rid of the maxl array if you just combine the first and third loop together, printing the max values as they are computed. Let me know if its not obvious how to do that.

Answer 4

To answer the issue of your program not working: findmax() returns a value that you store in maxr, but then you use maxr as an index, so you should have a function that returns the index of the maximum value instead of the value.

Edit (as barnes53 points out): actually, in the findmax() function, max is used as index and as value. At least "if (tab[j]>max) max=j;" must be "if (tab[j]>tab[max]) max=j;". And it would have helped me if the function was called findIndexOfMax().

Answer 5

Your program has O(n^2) time complexity due to the nested loops. But this can be done in linear time:

You already know how to find the biggest element to the left of each element: Iterate over all the elements, keeping track of the current maximum. The biggest element to the left of each element is the current maximum when you reach that element.

To find the biggest element to the right of each element, you do the same thing in reverse: iterate the array from right to left, keeping track of the current maximum.

So you'd have two loops (left to right and right to left), but they wouldn't be nested within each other, so performance would be much better for large arrays.

Answer 6

Use std::max_element and std::count. Or use std::for_each with custom class to find index yourself.

---

inline int findmax(int tab[], int beg, int end)
{
    int max=0;
    for (int j=beg; j<end; j++)
        if (tab[j]>max) max=j;
    return max;
}

Won't work if all elements in array are negative. Use std::numeric_limits<int>::min() for initial value.