一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最大值。
区间求极值的算法
#include<iostream> #include<algorithm> #include<cmath> using namespace std; int res[10][4] = { 0 };//ST表的大小 void fillSTForm(int src[], int n, int res[][4]) { int i, j; for (i = 0; i < n; i++) { res[i][0] = src[i]; } for (i = 1; (1<<i)<= n; i++)//1<<i相当于2^i,保证时间复杂度是log n { for (j = 0; j < n-(1 << i) + 1; j++) { res[j][i]= max(res[j][i-1],res[j+(1<<(i-1))][i-1]); } } } int searchSTData(int src[],int l,int r)//查表，取最大值 { int n =log2( r - l + 1);//向下取整 return max(res[l][n], res[r - (1 << n) + 1][n]); } int main() { int a[10] = { 1, -5, 8, 3, -4, 7, 6, -1, 2, 9 }; fillSTForm(a, 10, res);//填表 cout<<searchSTData(a,2,6)<<endl; /*for (int i = 0; i < 10; i++) //填表的输出 { for (int j = 0; j < 4; j++) { cout << res[i][j]<< ' '; } cout << endl; }*/ system("pause"); return 0; }