C ++ ищет самые большие числа в массиве

Question

Мне нужно посчитать наибольшее число в массиве слева и справа от фактического индекса. Я имею в виду, если мой массив

1, 3, 2, 4, 3;

Мне нужно вывести:

//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

Мне нужно сделать это ОЧЕНЬ быстро, поэтому плохая идея - просто сидеть слева, а потом справа. Я решил просто найти самый большой справа, а затем, когда я доберусь туда, посчитать следующий, и так далее. С наибольшим слева, только если фактический больше, чем это, измените его. Но что-то его не работает ... Программа иногда дает неправильный вывод. К сожалению, я не знаю, на каком входе это делает ...

Вот мой код, если вы видите какие-либо общие ошибки или ошибки в алгоритме, я буду рад, если вы сможете опубликовать его ...

#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: Я прочитал все ответы и реализовал это. Одна проблема заключается в том, что я не могу сохранить значения в первом цикле, поэтому я должен «объединить» два for для ... Вот мой код на данный момент:

#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

Ваша программа имеет O (n ^ 2) временную сложность из-за вложенных циклов. Но это можно сделать за линейное время:

Вы уже знаете, как найти самый большой элемент слева от каждого элемента: перебирайте все элементы, отслеживая текущий максимум. Самый большой элемент слева от каждого элемента - это текущий максимум при достижении этого элемента.

Чтобы найти самый большой элемент справа от каждого элемента, вы делаете то же самое в обратном порядке: перебираете массив справа налево, отслеживая текущий максимум.

Таким образом, у вас будет два цикла (слева направо и справа налево), но они не будут вложены друг в друга, поэтому производительность будет намного выше для больших массивов.

Answer 2

Улучшение принятого ответа:

Вы можете исключить не менее 25% (возможно, 50%) сравнений, пройдя половину пути.

Начинайте слева и вычисляйте «левый максимум» по ходу. Начните справа и вычислите «правильный максимум» по ходу движения.

После встречи в середине, сравните левый максимум с правым максимумом в месте встречи. Если они равны, то вы знаете ответ для остальных вычислений (вы сохранили 50% вычислений). Если они не равны, то вы должны продолжить вычисления на стороне, которая имеет больший максимум двух половин, до точки, где вы достигнете максимума на стороне на , и тогда вы знаете, ответ для остальной части этой стороны.

Answer 3

Чтобы ответить на вопрос о том, что ваша программа не работает: findmax () возвращает значение, которое вы храните в maxr, но затем вы используете maxr в качестве индекса, поэтому у вас должна быть функция, которая возвращает индекс максимального значения вместоЗначение.

Редактировать (как указывает barnes53): фактически, в функции findmax () max используется как индекс и как значение.По крайней мере "if (tab [j]> max) max = j;"должно быть "if (tab [j]> tab [max]) max = j;".И это помогло бы мне, если бы функция называлась findIndexOfMax ().

Answer 4

Используйте std :: max_element и std :: count . Или используйте std :: for_each с пользовательским классом, чтобы найти индекс самостоятельно.

---

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;
}

Не будет работать, если все элементы в массиве отрицательны. Используйте std::numeric_limits<int>::min() для начального значения.

Answer 5

Вот реализация того, о чем говорит interjay:

#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;
}

Звучит так, будто вы ограничены в памяти. В этом случае вы можете избавиться от массива maxl, если просто объедините первый и третий цикл, печатая максимальные значения по мере их вычисления. Дайте мне знать, если не очевидно, как это сделать.

Answer 6

stefaanv (приблизительно) идентифицировал вашу проблему, поэтому я просто покажу реализацию, которая не O (n ^ 2).

Редактировать: для минимального использования памяти

#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';
    }
}