Описание задачи: Вам дана последовательность неотрицательных чисел, и вам нужно найти подпоследовательность, произведение суммы чисел на минимальное число в которой является максимальным.

Это очень похоже на гистограмму POJ 2559. Вы можете использовать увеличивающийся стек, чтобы решить его за время O (n). Идея состоит в том, чтобы перебирать каждое число в последовательности и каждый раз принимать текущее число как минимальное число в подпоследовательности. Затем вам нужно найти самую длинную подпоследовательность (чтобы максимизировать сумму и, следовательно, произведение), в которой это число является минимальным. Мы сохраняем левую границу, чтобы знать, где начинается подпоследовательность, а правая граница — это первое число после текущего числа, которое меньше его.

Если новое число больше вершины стека, мы просто добавляем его. Если оно равно, то последовательные равные числа будут иметь одинаковые границы и, следовательно, одинаковые результаты, поэтому мы можем просто пропустить это. Если он больше, чем вершина стека, мы используем его индекс-1 в качестве правой границы и вычисляем требуемый продукт (предварительно необходимо сохранить массив сумм), используя вершину стека в качестве минимального числа в подпоследовательности. Левая граница по умолчанию - это сам индекс числа (в случае, когда он больше, чем числа перед ним), он должен быть обновлен до индекса новой вершины после извлечения (т.е. индекс первого числа перед ним, которое меньше это + 1).

Не забудьте добавить -1 в конец стека, чтобы он вычислял значения для чисел, оставшихся в стеке после повторения всех входных чисел.

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 100005
typedef long long ll;
ll numbers[MAXN], sums[MAXN]={0};
int stack[MAXN], left[MAXN];
//numbers store the actual numbers
//stack stores the index
int main(){
 int N, top=-1, L=1, R=1;
 ll tmp, ans=0;
 scanf("%d", &N);
 for(int i=1; i<=N; i++){
  scanf("%lld", numbers+i);
  sums[i] = sums[i-1] + numbers[i];
 }
 numbers[N+1] = -1;
//build an increasing stack
 for(int i=1; i<=N+1; i++){
  if(top<0 || numbers[i]>numbers[stack[top]]){
   stack[++top] = i;
   left[i] = i;
  }
  else{
   if(numbers[i]==numbers[stack[top]]){
    continue;
   }
while(top>=0 && numbers[i]<numbers[stack[top]]){
    tmp = numbers[stack[top]]*(sums[i-1]-sums[left[stack[top]]-1]);
    if(tmp > ans){
     ans=tmp;
     L = left[stack[top]];
     R = i-1;
    }
    top--;
   }
   left[i] = left[stack[++top]];
   stack[top] = i;
  }
 }
 printf("%lld\n", ans);
 printf("%d %d\n", L, R);
}