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

编辑:我已阅读所有回复并实施了它.一个问题是我不能将值存储在第一个循环中,所以我必须将两个"合并"为...这是我现在的代码:

#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)时间复杂度.但这可以在线性时间内完成:

您已经知道如何找到每个元素左侧的最大元素:迭代所有元素,跟踪当前最大值.每个元素左边最大的元素是当你到达那个元素时的当前最大值.

要找到每个元素右侧的最大元素,您可以反向执行相同的操作:从右向左迭代数组,跟踪当前最大值.

所以你有两个循环(从左到右和从右到左),但它们不会相互嵌套,因此对于大型数组来说性能要好得多.