【今日头条】非负整数数组，求子序列和与最小值乘积的最大值。

1、题目描述

一个非负数组，例如【1，0， 3， 2，5】，求数组的一个子序列，使得子序列的和与子序列的最小值的乘积最大。

2、问题描述：

3、问题关键：

• 单调队列。
• 求一个使得每一个数为最小值的最长区间。
• 添加哨兵。

4、C++代码：

#include <iostream>

using namespace std;

const int N = 1000010;

int n;
int q[N], d[N];//q保存数组的下标。 d是保存的数组。
int le[N], ri[N];//le保存的是i的最比第i个位置值小的下一个位置。
                //ri保存的第i个位置元素为最小值的时候，右边比i位置小的元素的前一个位置。

int main() {
    cin >> n; 
    for (int i = 1; i <= n; i ++) cin >> d[i];
    d[0] = d[n + 1] = -1;//这是两个哨兵，保证数组的元素
    int tt = 0;
    q[0] = d[0];
    for (int i = 1; i <= n; i ++) {//求i位置的左边比i位置小的元素的下一个位置。
        while(d[q[tt]] >= d[i]) tt --;//
        le[i] = q[tt] + 1;
        q[++ tt] = i;
    }
    tt = 0;
    q[0] = n + 1;
    for (int i = n; i > 0; i --) {
        while(d[q[tt]] >= d[i]) tt --;
        ri[i] = q[tt] - 1;
        q[++ tt] = i;
    }
    d[0] = 0;
    for (int i = 1; i <= n; i ++) d[i] += d[i - 1];

    int res = 0;
    for (int i = 1; i <= n; i ++) res = max(res, (d[i] - d[i - 1]) * (d[ri[i]] - d[le[i] - 1]));

    cout << res << endl;
    return 0;
}