3
정수 N 주어진 경우 정수 N에 대한 PermutationSum은 1에서 N까지의 모든 숫자 배열에서 인접한 요소의 최대 차이로 정의되는 PermutationSum을 알아야합니다.인접한 요소의 차이의 합을 최대화하십시오.
예 보자 N = 3 다음 않음 3
설명은 : N = 3의 경우, 가능한 배열은 : 장치 용 PermutationSum의
{1,2,3}
{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}
{3,2,1}
값은 {1,2,3} 2 개, 즉 ABS 인 (1-2) + abs (2-3) = 2
배치 용의 PermutationSum 451,515,값 {1,3,2}의 배치를위한 PermutationSum 3.
값은 {2,1,3}를 배치 {2,3-위한 PermutationSum 3.
값은 1}에 대한 구성 PermutationSum 3.
값은 {3,1,2}는 배열을위한 PermutationSum 3.
값 {3,2,1}를 따라서 2
이다 PermutationSum의 최대 값 모든 준비는 우리는 N이 100000
내가 N이 최대 개까지입니다 주어진 N이 최대 값을 찾아야 3.
입니다! 해결책. 하지만 큰 N에 대해서는 작동하지 않습니다.
나는 훨씬 쉬운 조합 솔루션이 있다고 생각합니다. 기본적으로, 큰 차이가있는 요소를 서로 옆에 배치하여 개별적인 요약이 최대화되도록하는 것이 좋습니다. 단지 아이디어 일뿐입니다. – Codor