POJ-2796(单调栈)

单调栈的运用：

一系列数中取一个子序列使得子序列和乘以子序列中的最小值使得这个值最大。

思想：

要保证自己是一段区间的最小值，如何保证自己是区间的最小值呢？
找出比自己小的数，不加入区间，自己就不是最小的了.....
从当前数向左遍历找出比自己小的第一个数的下标，从当前的数向右遍历，找出比自己小的第一个数的下标，那么区间就可以保证当前的数是最小的啦！！！！

Feel Good

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#define ll long long
using namespace std;
int R[101000],L[101000];
int a[101000];
ll sum[101000];
stack<int>s;
int main( )
{
      int n;
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
      {
            scanf("%d",&a[i]);
            if(i==1)
            {
                  sum[1]=a[1];
            }
            else
            {
                  sum[i]=sum[i-1]+a[i];
            }

      }
      for(int i=1;i<=n;i++)
      {
            while(!s.empty( )&&a[s.top( )]>=a[i])//找出每个数向左遍历比自己小的第一个数
            {
                  s.pop( );
            }
            if(s.empty( ))
            {
                  L[i]=0;
            }
            else
            {
                  L[i]=s.top( );
            }
            s.push(i);
      }
      /*for(int i=1;i<=n;i++)
      {
            cout<<L[i]<<" ";
      }
      cout<<endl;*/
      while(!s.empty( ))
      {
            s.pop( );
      }
      for(int i=n;i>0;i--)
      {
            while(!s.empty( )&&a[s.top( )]>=a[i])//找出每个数向右遍历比自己小的第一个数
            {
                  s.pop( );
            }
            if(s.empty( ))
            {
                  R[i]=n+1;
            }
            else
            {
                  R[i]=s.top( );
            }
            s.push(i);
      }
      /*for(int i=1;i<=n;i++)
      {
            cout<<R[i]<<" ";
      }
      cout<<endl;*/
      ll ans=-1;
      int left=1;
      int right=1;
      for(int i=1;i<=n;i++)
      {
            if(ans<(sum[R[i]-1]-sum[L[i]])*a[i])
            {
                  ans=(sum[R[i]-1]-sum[L[i]])*a[i];
                  left=L[i]+1;
                  right=R[i]-1;
            }
      }
      printf("%lld\n",ans);
      printf("%d %d\n",left,right);
      return 0;
}