21xrx.com
2025-03-22 22:26:14 Saturday
文章检索 我的文章 写文章
C++编程实践：求长度为n的序列的最大值和最小值
2023-07-08 10:05:59 深夜i     29     0
C++编程 实践 序列 最大值 最小值

在C++编程领域，求解长度为n的序列的最大值和最小值是一个非常基础而又常见的问题。这个问题虽然看起来很简单，但是在算法实现和代码优化上还是需要花费一些时间和精力的。

首先，我们可以采用最朴素的方法，即遍历整个序列，记录当前最大值和最小值，这样可以得到序列的最大值和最小值。代码实现如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int maxn=-1000000000,minn=1000000000;
  for(int i=1;i<=n;i++)
  {
    int x;
    cin>>x;
    maxn=max(maxn,x);
    minn=min(minn,x);
  }
  cout<<maxn<<" "<<minn<<endl;
  return 0;
}

这段代码看起来很简单，但是时间复杂度却是O(n)，当n很大时，计算量也会非常大。为了提高效率，我们可以采用分治法，将序列分为两部分，在两部分中求得最大值和最小值，最后再将两部分的结果合并，得到整个序列的最大值和最小值。代码实现如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000;
int a[MAXN+5];
struct node
  int maxnans;
node solved(int l,int r)
{
  if(l==r) //边界情况
  {
    ans.maxn=a[l];
    ans.minn=a[l];
    return ans;
  }
  int mid=(l+r)/2;
  node left=solved(l,mid);
  node right=solved(mid+1,r);
  ans.maxn=max(left.maxn,right.maxn);
  ans.minn=min(left.minn,right.minn);
  return ans;
}
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i];
  node result=solved(1,n);
  cout<<result.maxn<<" "<<result.minn<<endl;
  return 0;
}

该算法的时间复杂度是O(nlogn)，效率会比最朴素的方法高很多。

最后，我们需要注意的是，对于一些特定的序列，我们还可以采用其他的算法，例如堆排序、归并排序等。因此，在实际应用中，我们需要根据情况灵活选择不同的算法。

  
  

评论区