Функция MaxExpressionValue(nums []int) int принимает на вход слайс nums.
Найдите максимальное значение выражения nums[s] — nums[r] + nums[q] — nums[p], где p, q, r и s — индексы слайса, а
s
>
r
>
q
>
p
s
>
r
>
q
>
p
s>r>q>p.
Например, для nums := []int{3, 9, 10, 1, 30, 40} функция должна вернуть значение 46 (поскольку 40 – 1 + 10 – 3 – максимально).
Задачу надо решить, используя принципы динамического программирования.
func MaxExpressionValue(nums []int) int {
n := len(nums)
dp1 := make([][]int, n)
dp2 := make([][]int, n)
for i := range dp1 {
dp1[i] = make([]int, n)
dp2[i] = make([]int, n)
}
for len := 2; len <= n; len++ {
for l := 0; l <= n-len; l++ {
r := l + len - 1
dp1[l][r] = max(dp1[l+1][r], nums[r] - nums[l])
}
}
for len := 2; len <= n; len++ {
for r := n-1; r >= len-1; r-- {
l := r - len + 1
dp2[l][r] = max(dp2[l][r+1], nums[r] - nums[l])
}
}
maxVal := 0
for s := 1; s < n-2; s++ {
for r := s-1; r > 0; r-- {
for q := n-1; q > r; q-- {
for p := 0; p < q-1; p++ {
val := dp1[s][r] + dp2[q][p]
if val > maxVal {
maxVal = val
}
}
}
}
}
return maxVal
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет