입력 | 출력 |
---|---|
6 20 1 15 8 4 10 | 62 |
: 순서 중요. permutations 이용
재귀 및 백트래킹으로 풀 수 있다.
from itertools import permutations
n = int(input())
nums = list(map(int, input().split()))
per = list(permutations(nums, n))
maxi = -1e9
for p in per:
maxi = max(maxi, sum(abs(p[i]-p[i+1]) for i in range(n-1)))
print(maxi)
def dfs(depth):
global maxi
if depth == n:
sumi = 0
for i in range(n-1):
sumi += abs(arr[i]-arr[i+1])
maxi = max(sumi, maxi)
return
for i in range(n):
if visited[i]:
continue
arr.append(nums[i])
visited[i] = 1
dfs(depth+1)
visited[i] = 0
arr.pop()
n = int(input())
nums = list(map(int, input().split()))
arr = []
visited = [0]*n
maxi = -1e9
dfs(0)
print(maxi)