max sub sum

dairongpeng · dairongpeng · commit 0c7e04b36bfa · 2022-03-20T19:57:24.000+08:00
diff --git a/13-《进阶》单调栈和窗口.md b/13-《进阶》单调栈和窗口.md
@@ -419,74 +419,81 @@ func main() {
 
 给定一个只包含正整数的数组arr，arr中任何一个子数组sub，一定都可以算出(sub累加和)*(sub中的最小值)是什么，那么所有子数组中，这个值最大是多少？
 
-```Java
-
-package class01;
-
-import java.util.Stack;
+```Go
+package main
 
-public class Code04_AllTimesMinToMax {
+import (
+	"fmt"
+	"math"
+)
 
-	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);
+// 给定一个正整数数组，求子数组中，累加和乘以数组中最小值。所有子数组中算出的最大值返回
+func max1(arr []int) int {
+	max := math.MinInt
+	for i := 0; i < len(arr); i++ {
+		for j := i; j < len(arr); j++ {
+			minNum := math.MaxInt
+			sum := 0
+			for k := i; k <= j; k++ {
+				sum += arr[k]
+				minNum = int(math.Min(float64(minNum), float64(arr[k])))
 			}
+			max = int(math.Max(float64(max), float64(minNum * sum)))
 		}
-		return max;
 	}
+	return max
+}
 
-	public static int max2(int[] arr) {
-		int size = arr.length;
-		int[] sums = new int[size];
-		sums[0] = arr[0];
-		for (int i = 1; i < size; i++) {
-			sums[i] = sums[i - 1] + arr[i];
-		}
-		int max = Integer.MIN_VALUE;
-		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;
+func max2(arr []int) int {
+	size := len(arr)
+	sums := make([]int, size)
+
+	sums[0] = arr[0]
+	for i := 1; i < size; i++ {
+		sums[i] = sums[i - 1] + arr[i]
 	}
 
-	public static int[] gerenareRondomArray() {
-		int[] arr = new int[(int) (Math.random() * 20) + 10];
-		for (int i = 0; i < arr.length; i++) {
-			arr[i] = (int) (Math.random() * 101);
+	max := math.MinInt
+	stack := make([]int, 0)
+
+	for i := 0; i < size; i++ {
+		for len(stack) != 0 && arr[stack[len(stack) - 1]] >= arr[i] {
+			// stack pop
+			j := stack[len(stack) - 1]
+			stack = stack[:len(stack) - 1]
+
+			m := math.MinInt
+			if len(stack) == 0 {
+				m = sums[i - 1]
+			} else {
+				m = sums[i - 1] - sums[stack[len(stack) - 1]]
+			}
+
+			max = int(math.Max(float64(max), float64(m * arr[j])))
 		}
-		return arr;
+		stack = append(stack, i)
 	}
 
-	public static void main(String[] args) {
-		int testTimes = 2000000;
-		System.out.println("test begin");
-		for (int i = 0; i < testTimes; i++) {
-			int[] arr = gerenareRondomArray();
-			if (max1(arr) != max2(arr)) {
-				System.out.println("FUCK!");
-				break;
-			}
+	for len(stack) != 0 {
+		j := stack[len(stack) - 1]
+		stack = stack[:len(stack) - 1]
+
+		m := math.MinInt
+		if len(stack) == 0 {
+			m = sums[size - 1]
+		} else {
+			m = sums[size - 1] - sums[stack[len(stack) - 1]]
 		}
-		System.out.println("test finish");
+
+		max = int(math.Max(float64(max), float64(m * arr[j])))
 	}
 
+	return max
 }
 
+func main() {
+	arr := []int{3, 4, 1, 7, 3, 9, 12, 62, 82, 91, 30}
+	fmt.Println(max1(arr))
+	fmt.Println(max2(arr))
+}
 ```
