package q3640

import "math"

type node struct {
	pos int
	dir int8
}

const (
	NEUTRAL int8 = iota
	ASCEND
	DESCEND
)

func maxSumTrionic(nums []int) int64 {
	nodes := [4]node{}
	pfSum := make([]int, len(nums)+1) // prefix sum
	pfSum[1] = nums[0]
	var maxSum = math.MinInt

	var currentDir int8
	for i := 1; i < len(nums); i++ {
		switch {
		case nums[i] == nums[i-1]:
			currentDir = NEUTRAL
		case nums[i] < nums[i-1]:
			currentDir = DESCEND
		default:
			currentDir = ASCEND
		}

		if currentDir != nodes[3].dir {
			nodes[0], nodes[1], nodes[2] = nodes[1], nodes[2], nodes[3]
			nodes[3] = node{
				pos: i,
				dir: currentDir,
			}
			for j := nodes[0].pos + 1; j < nodes[1].pos; j++ {
				if pfSum[j] < pfSum[nodes[0].pos] {
					nodes[0].pos = j
				}
			}
		} else {
			nodes[3].pos = i
		}

		pfSum[i+1] = nums[i] + pfSum[i]

		if nodes[1].dir == ASCEND && nodes[2].dir == DESCEND && nodes[3].dir == ASCEND {
			curSum := pfSum[i+1] - pfSum[nodes[0].pos]
			maxSum = max(curSum, maxSum)
		}
	}

	return int64(maxSum)
}

var _ = maxSumTrionic