POJ2796 Feel Good（单调栈）

February 05, 2016

题目链接

题意：找到一个区间，使区间和与区间内元素的乘积最大。输出这个最大值和区间端点。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int h[100005];
long long sum[100005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n)!=EOF){
        long long ans = 0, l = 1, r= 1;
        sum[0] = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &h[i]);
            sum[i] = sum[i-1]+h[i];
        }
        stack<int> s;
        s.push(0);
        h[++n] = 0;
        for(int i = 1; i <= n; i++){
            while(h[i] < h[s.top()]){
                long long a = h[s.top()];
                s.pop();
                long long b = sum[i-1]-sum[s.top()];
                long long tem = a*b;
                if(tem > ans){
                    ans = tem;
                    l = s.top()+1;
                    r = i-1;
                }

            }
            s.push(i);
        }
        cout << ans << endl;
        cout << l << " " << r << endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]