给定一个只包含正数的数组 arr，arr 中任何一个子数组 sub，一定都可以算出 （sub累加和） * （sub中的最小值） 是什么，那么所有子数组中，这个值最大是多少？
注意：子数组一定是连续的序列。
求得以每个位置的值为最小值的子数组的“累加和 * 最小值” 的结果，选出其中的最大值即为答案。
问：那么如何使得必须以 i i i 位置的 x x x 为最小值的子数组的累加和最大呢？
答：求得 x x x 左边第一个比它小的数在 j j j 位置，右边第一个比它小的数在 k k k 位置，那么 [ j + 1 , k − 1 ] [j + 1, k-1] [j+1,k−1] 范围的数全部都要。
一定要以 x x x 为最小值的子数组，那么就是求 s u m ∗ x sum * x sum∗x 最大， x x x 已经确定，只需要 s u m sum sum 最大，因为全部是正数，所以包含的数的个数越多， s u m sum sum 越大。即以 x x x 为最小值的子数组中包含的个数越多， s u m sum sum 就越大。
总结步骤如下：
数组中可能会存在重复值，但是使用单调栈的时候仍然保存单个的值而非使用链表或数组来保存，因为相等情况做错化处理，Java代码中注释对重复值情况做了举例说明。
public class AllTimesMinToMax {
//暴力方法，时间复杂度O(n^3)
public static int max1(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
int minNum = Integer.MAX_VALUE;
int sum = 0;
for (int k = i; k <= j; k++) {
sum += arr[k];
minNum = Math.min(minNum, arr[k]);
}
max = Math.max(max, minNum * sum);
}
}
return max;
}
public static int max2(int[] arr) {
int size = arr.length;
int[] sums = new int[size]; //前缀和数组
sum[0] = arr[0];
//生成前缀和数组
for (int i = 1; i < size; i++) {
sum[i] = sum[i - 1] + arr[i];
}
//单调栈
int max = Integer.MIN_VALUE;
//数组中可能存在重复值，为什么这里栈中放的是单个的值，而不是链表list?
//解释：相等情况做错化处理，如果有几个相等值，可能有些位置计算的结果不对，但是没关系，总会有个位置的值计算结果是正确的
//例子：
// [3, 4, 3, 4, 3, 2]
// 0 1 2 3 4 5
//0 和 2 位置的 3 计算的时候结果都是错的，但是没关系就让它错着，4位置的3最终会算对一个结果，这些相等的3是可以连通的
// [1, 2, 2, 2, 2, 2, 1]
// 0 1 2 3 4 5 6
// 极端例子：
// 入栈顺序 : 栈中情况
// 0->1 0->1
// 1->2 1->2
// 2->2 1->2出栈，左边扩到0位置（到不了），右边2位置（到不了），所以只有1位置的2自己成为子数组，结果是2*2=4不对
// 0->1, 2->2
// 3->2 2->2出栈，左边扩到0（到不了），右边扩到3（到不了），只有1->2 和 2->2，结果为8不对
// 0->1, 3->2
// 4->2 3->2出栈，左边扩到0（到不了），右边扩到4（到不了），只有1->2、2->2、3->2，结果为12不对
// 0->1，4->2
// 5->2 4->2出栈，左边扩到0（到不了），右边扩到5（到不了），只有1/2/3/4位置的2，结果为16不对
// 0->1，5->2
// 6->1 5->2出栈，左边扩到0,右边扩到6，则范围中包含了1/2/3/4/5位置的2，结果为10*2=20正确,这就是所谓的连通，相等的值总会有一个在出栈的时候扩充到正确的范围
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < size; i++) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) { //遇到相等也弹出
int j = stack.pop();
max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
}
return max;
}
}
/*************************************************************************
> File Name: 002.AllTimesMinToMax.cpp
> Author: Maureen
> Mail: Maureen@qq.com
> Created Time: 一 11/28 17:12:19 2022
************************************************************************/
#include