POJ 2796 Feel Good(单调栈)

Description

给出一个序列，要求的是一个区间，这个区间的最小值乘以这个区间所有数字的和是最大值。求这个最大值与这个区间。

单调栈+前缀和

#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long
const int N = 100100;

int h[N];
int L[N], R[N];
ll sum[N];
stack<int> sk;

///单调栈维护了一个单调递增序列
///单调栈:栈内越靠近栈顶的下标所对应的高度越高
///但栈内所存的，终究还是下标
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &h[i]);
            sum[i] = sum[i - 1] + h[i];
        }

        while(!sk.empty())
            sk.pop();

        for(int i = 1; i <= n; ++i)
        {
            while(!sk.empty() && h[sk.top()] >= h[i])
                sk.pop();

            if(sk.empty())
                L[i] = 0;///最小下标 - 1
            else
                L[i] = sk.top();
            sk.push(i);
        }

        while(!sk.empty())
            sk.pop();

        for(int i = n; i >= 1; --i)
        {
            while(!sk.empty() && h[sk.top()] >= h[i])
                sk.pop();

            if(sk.empty())
                R[i] = n + 1;///最大下标 + 1
            else
                R[i] = sk.top();
            sk.push(i);
        }

        ll ans = 0, tem = 0, ansL = 1, ansR = 1;///初始化是针对'0'的,想好了再写
        for(int i = 1; i <= n; ++i)
        {
            tem = h[i] * (sum[ R[i] - 1 ] - sum[ L[i] ]);
            if(ans < tem)
            {
                ans = tem;
                ansL = L[i] + 1;
                ansR = R[i] - 1;
            }
        }
        cout << ans << '\n';
        cout << ansL << ' ' << ansR << '\n';
    }
    return 0;
}

注意初始化的值，注意if(empty)时的赋值

分别是：最小下标 - 1，最大下标 + 1