题解 | 子数组的最大累加和问题

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}

		arr := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			arr[i], _ = strconv.Atoi(scanner.Text())
		}
		fmt.Println(process(arr))
	}
}

func process(arr []int) int {
	maxv := arr[0]
	pre := arr[0]
	for i := 1; i < len(arr); i++ {
	   // 在i位置处，求每个地方的最大值，只有2种可能性
	   // pre代表[0,i-1]处最大值，若pre大于等于0， i位置处最大值为pre+arr[i]
	   // 若pre小于0，i处最大值为arr[i]
		pre = max(pre+arr[i], arr[i])
		maxv = max(maxv, pre)
	}
	return maxv
}
func max(a, b int) int {
    if a>b {
        return a
    }
    return b
}