笔试刷题-头条2018-07-10

题目描述：

/**
给定一个数组序列, 需要求选出一个区间,
使得该区间是所有区间中经过如下计算的值最大的一个：
区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，
不需要输出具体的区间。
如给定序列  [6 2 1]则根据上述公式,
可得到所有可以选定各个区间的计算值:
[6] = 6 * 6 = 36;
[2] = 2 * 2 = 4;
[1] = 1 * 1 = 1;
[6,2] = 2 * 8 = 16;
[2,1] = 1 * 3 = 3;
[6, 2, 1] = 1 * 9 = 9;
从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。
区间内的所有数字都在[0, 100]的范围内;
输入描述:
第一行输入数组序列长度n，第二行输入数组序列。
对于 50%的数据,  1 <= n <= 10000;
对于 100%的数据, 1 <= n <= 500000;
输出描述:
输出数组经过计算后的最大值。
输入例子1:
3
6 2 1
输出例子1:
36
*/

思路如下：

类似柱状图扩展长方形求最大面积即可
用栈更新一个点可以向左扩展到哪里，向右可以扩展到哪里
然后用计算累加和即可

代码如下：

#include<stdio.h>
#include<iostream>
#include<stack>
 
#define MAX_N 500005
 
using namespace std;
 
int val[MAX_N], accSum[MAX_N];
int leftNum[MAX_N], rightNum[MAX_N];
 
int main(){
    int N;
    scanf("%d", &N);
    for(int i=1; i<=N; i++){
        scanf("%d", val+i);
        accSum[i]=accSum[i-1]+val[i];
    }
    //用栈构建left right
    stack<int> st;
    //建立left
    for(int i=1; i<=N; i++){
        if(st.empty() || val[st.top()]<val[i]){
            if(st.empty()){
                leftNum[i]=0;
            }
            else{
                leftNum[i]=st.top();
            }
            st.push(i);
        }
        else{
            while(!st.empty() && val[st.top()]>=val[i]){
                st.pop();
            }
            if(st.empty()){
                leftNum[i]=0;
            }
            else{
                leftNum[i]=st.top();
            }
            st.push(i);
        }
    }
    //清空
    while(!st.empty()){
        st.pop();
    }
    //建立right
    for(int i=N; i>=1; i--){
        if(st.empty() || val[st.top()]<val[i]){
            if(st.empty()){
                rightNum[i]=N+1;
            }
            else{
                rightNum[i]=st.top();
            }
            st.push(i);
        }
        else{
            while(!st.empty() && val[st.top()]>=val[i]){
                st.pop();
            }
            if(st.empty()){
                rightNum[i]=N+1;
            }
            else{
                rightNum[i]=st.top();
            }
            st.push(i);
        }
    }
//    for(int i=1; i<=N; i++){
//        printf("%d ", leftNum[i]);
//    }
//    printf("\n");
//    for(int i=1; i<=N; i++){
//        printf("%d ", rightNum[i]);
//    }
//    printf("\n");
    int res=0;
    for(int i=1; i<=N; i++){
        int curNum=val[i]*((accSum[i-1]-accSum[leftNum[i]])+(accSum[rightNum[i]-1]-accSum[i])+val[i]);
        res=max(res, curNum);
    }
    printf("%d", res);
    return 0;
}