Skip to content

Instantly share code, notes, and snippets.

@yojkim

yojkim/SumofSubarrayMinimums.go

Created October 6, 2018 02:05
Show Gist options
  • Save yojkim/c32e49e83e20844f4d5355525ae0f48a to your computer and use it in GitHub Desktop.
Save yojkim/c32e49e83e20844f4d5355525ae0f48a to your computer and use it in GitHub Desktop.
Download ZIP
Raw
SumofSubarrayMinimums.go
func sumSubarrayMins(A []int) int {
dp := make([]int, len(A)+1)
stack := []int{-1}
res := 0
for i, n := range A {
for stack[len(stack)-1] != -1 && n <= A[stack[len(stack)-1]] {
stack = stack[:len(stack)-1]
}
dp[i+1] = dp[stack[len(stack)-1] + 1] + (i - stack[len(stack)-1]) * n
stack = append(stack, i)
res += dp[i+1]
}
fmt.Println(dp)
return res % 1000000007
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment