B.寻找最大值

算法：

1.正向思维如果枚举区间求最值肯定TLE，数据量很大。

2.反向思维，枚举每个点的左右区间，虽然两个for循环，我感觉是平均是O（N）的时间复杂度，动态规划的思想，可以求出。

3.这题相当诡异，不能给dt数组清空赋值，坑了我一晚上加上午，还不知道为什么。

4.我的L[I]记录的是该点能往左到达的边界，R【i]是往右到达的边界。旭他们记录的是以该点向左能扩张的长度，R【i]类似。

View Code #include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<vector> #include<string> #include<math.h> #include<map> #include<set> #include<algorithm> using namespace std; const long long inf = -(1LL<<60); int N; long long dt[201000]; //输入数据 long long sum[201000]; //静态，不需要修改，数组维护最长前缀和 long long L[201000]; long long R[201000];int main( ) {while( scanf("%d",&N) != EOF){memset(sum, 0, sizeof(sum));for(int i = 1; i <= N; i++){ scanf("%I64d",&dt[i]);sum[i] = sum[i-1] + dt[i];}memset(L,0,sizeof(L));memset(R,0,sizeof(R));for(int i = 1; i <= N; i++){ int j = i-1, len = 0;while(j >= 1){if( dt[i] > dt[j] ) break;else{len += 1+L[j];j = j-L[j]-1; } }L[i] = len;}for(int i = N; i >= 1; i--){ int j = i+1, len = 0;while(j <= N ){if( dt[i] > dt[j] ) break;else{len += 1+R[j];j = j+R[j]+1; } }R[i] = len;}long long maxn = inf;long long ans;for( int i = 1; i <= N; i++){int l = i-L[i];int r = i+R[i];ans = (sum[r] - sum[l - 1]) * dt[i];if( ans > maxn )maxn = ans;}printf("%I64d\n",maxn); }return 0; }

 

View Code #include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<vector> #include<string> #include<math.h> #include<map> #include<set> #include<algorithm> using namespace std; const long long inf = (1LL<<60); int N; long long dt[301000]; //输入数据 long long sum[301000]; //静态，不需要修改，数组维护最长前缀和 int L[301000]; int R[301000];int main( ) { while( scanf("%d",&N) != EOF){ for(int i = 1; i <= N; i++){ scanf("%I64d",&dt[i]);sum[i] = sum[i-1] + dt[i];}memset(L,0,sizeof(L));memset(R,0,sizeof(R));for(int i = 1; i <= N; i++){ if( dt[i] == dt[i-1] && i != 1){L[i] = L[i-1];continue; }if( dt[i] > dt[i-1] || i == 1){L[i] = i; }else{ int j = i;while( --j ){ int x = L[j];if( dt[x - 1] < dt[i] ){L[i] = x; break; } }} }for( int i = N; i >= 1; i--){ if( dt[i] == dt[i+1] && i != N){R[i] = R[i+1];continue; } if( dt[i] > dt[i+1] || i == N){R[i] = i; }else{ int j = i;while( ++j <= N ){ int x = R[j];if( dt[x + 1] < dt[i] ){R[i] = x; break; } }} }long long maxn = -inf;for( int i = 1; i <= N; i++){long long ans = (sum[R[i]] - sum[L[i] - 1]) * dt[i];if( ans > maxn )maxn = ans;}printf("%I64d\n",maxn);}return 0; }

转载于:https://www.cnblogs.com/tangcong/archive/2012/08/18/2645085.html

总结

以上是生活随笔为你收集整理的B.寻找最大值的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。