解题思路:前缀和 + 单调栈
* a.既然要求区间和,那么就一定少不了前缀和
* b.构建nums数组的单调栈信息,要包括每个nums[i]的上一个更小值和下一个更小值信息
* c.从左到右遍历数组,以某个i位置作为最小值,利用单调栈快速获知他上一个更小值和下一个更小值
* 从而知道以nums[i]作为最小值的区间范围
* d.输出指标A的最大值
思路很简单但是因为我的单调栈写法不是很标准而且我的前缀和数组 和 dp数组没有统一长度,故在计算max值时,各位看官极有可能会看不懂代码。个人感觉,该题重在思路,如果思路懂的话,也能按照自己的想法实现函数的.

import java.util.*;  public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可      *      * 找到指标A最大的值      * @param arr int整型一维数组 给定的数组      * @return int整型      */     public int max (int[] arr) {         int[] pSum = new int[arr.length+1];         for(int i=1;i<=arr.length;i++){             pSum[i] = arr[i-1] + pSum[i-1];         }          //构建单调栈,形成辅助数组信息         //dp[i][0]代表arr[i]的上一个更小值的位置,不存在则是-1         //同理dp[i][1]代表arr[i]的下一个更小值的位置         Deque> st = new ArrayDeque();         LinkedList list = new LinkedList();         list.offer(0);         st.offerLast(list);         int[][] dp = new int[arr.length][2];         for (int i = 0; i < dp.length; i++) {             Arrays.fill(dp[i],-1);         }         for(int i=1;i<arr.length;i++){             //当进栈元素比栈顶小，栈顶要退栈同时记录信息             while(!st.isEmpty()&&arr[i]<arr[st.peekLast().getLast()]){                 list = st.pollLast();                 for(int j=0;j<list.size();j++){                     //该链表上的所有节点的下一个更小值的下标都是i                     dp[list.get(j)][1] = i;                 }             }              //相同             if(!st.isEmpty()&&arr[i]==arr[st.peekLast().getLast()]){                 //arr[i]的上一个更小数也是dp[st.peekLast().getLast()][0]的下标                 dp[i][0] = dp[st.peekLast().getLast()][0];                 st.peekLast().offerLast(i);             }             //更大             else{                 //当栈不为空时,栈顶元素既为上一个更小数                 if(!st.isEmpty())                     dp[i][0] = st.peekLast().getLast();                 //当前数进栈                 list = new LinkedList();                 list.offerLast(i);                 st.offerLast(list);             }         }          //当数组遍历完,但是栈中还有元素         while(!st.isEmpty()){             list = st.pollLast();             //如果栈顶元素存在             if(!st.isEmpty()){                 for(int j=0;j<list.size();j++){                     //该链表上的所有节点的上一个更小值的下标都是栈顶元素                     dp[list.get(j)][0] = st.peekLast().getLast();                 }             }             //否则就是-1         }          //计算结果         int max = 0;         for (int i = 0; i < dp.length; i++) {             //注意利用前缀和计算[l~r]的区间和公式:res = pSum[r] - pSum[l-1];             // 但是这里dp[i]对应的是上一个更小的数的下标,是闭区间             // 但是pSum为了统一公式,又向前开多开了一个空间             int sum = pSum[dp[i][1]==-1 ?arr.length-1+1 :dp[i][1]-1+1]                     - pSum[dp[i][0]==-1 ?0 :dp[i][0]+1];             max = Math.max(max,sum*arr[i]);         }          return max;     } }