Как решить задачу на ДП на GOLANG?

Question

Как решить задачу на ДП на GOLANG?

галина семенова Ученик (93), на голосовании 1 год назад

Функция MaxExpressionValue(nums []int) int принимает на вход слайс nums.

Найдите максимальное значение выражения nums[s] — nums[r] + nums[q] — nums[p], где p, q, r и s — индексы слайса, а s > r > q > p s > r > q > ps>r>q>p.

Например, для nums := []uint{3, 9, 10, 1, 30, 40} функция должна вернуть значение 46 (поскольку 40 – 1 + 10 – 3 - максимально).

Задачу надо решить, используя принципы динамического программирования.

Примечания
В качестве решения надо отправить функцию MaxExpressionValue и все вспомогательные функции, которые вам потребуются.

Answer 1

Че-то я долго с этой задачей маялся. Вроде все условия соблюдены, комментарии к коду прилагаются :)

 package main 
 
import ( 
	"fmt" 
	"math" 
) 
 
// принимаем на вход слайс чисел с возвратом макс. 
// значения выражения nums[s] - nums[r] + nums[q] - nums[p] 
func MaxExpressionValue(nums []int) int { 
	n := len(nums) 
	if n < 4 { 
		return 0 
	} 
 
	// создаем двумерный массив dp размером 4 x n 
	dp := make([][]int, 4) 
	for i := range dp { 
		dp[i] = make([]int, n) 
	} 
 
	// инициализируем первый столбец массива dp 
	dp[0][0] = -nums[0] 
	dp[1][0] = math.MinInt32 
	dp[2][0] = math.MinInt32 
	dp[3][0] = math.MinInt32 
 
	// проходим по каждому элементу в nums (начиная со второго элемента) 
	for i := 1; i < n; i++ { 
		// обновляем каждую строку в dp на основе 
                // предыдущего значения в этой строке и нового значения 
		dp[0][i] = max(dp[0][i-1], -nums[i]) 
		dp[1][i] = max(dp[1][i-1], dp[0][i-1]+nums[i]) 
		dp[2][i] = max(dp[2][i-1], dp[1][i-1]-nums[i]) 
		dp[3][i] = max(dp[3][i-1], dp[2][i-1]+nums[i]) 
	} 
 
	// возврат последнего в последней строке dp (макс. значение выражения) 
	return dp[3][n-1] 
} 
 
// функция для возврата максимального из двух чисел 
func max(a, b int) int { 
	if a > b { 
		return a 
	} 
	return b 
} 
 
func main() { 
	nums := []int{3, 9, 10, 1, 30, 40} 
	fmt.Println(MaxExpressionValue(nums)) // 46 
}