牛客网真题-71-选区间

• 思路1：暴力,计算sum*min 50%
• 思路2：中心扩展法，把当前作为区间最小值，向两边扩展区间 100% 1400+ ms
• 思路3：由于数据范围从0-100，分别找出0-100每个数对应的最大和区间(见讨论区大佬)，类似查表法
• 思路4：单调栈(最佳思路)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        buff.readLine();
        int[] in = Arrays.stream(buff.readLine().split(" ")).parallel().mapToInt(Integer::parseInt).toArray();
        int res = 0;
        //中心扩展法
        for(int i = 0; i < in.length; i++){
            int p = i, q = i - 1;
            int sum = 0;
            while (p<in.length && in[p]>=in[i]) {
                sum += in[p];
                p++;
            }
            while (q >= 0 && in[q]>=in[i]) {
                sum += in[q];
                q--;
            }
            res = Math.max(res, sum * in[i]);
        }
        System.out.println(res);
    }
}