问题描述
给定一个整数N.我们需要找出PermutationSum整数N被定义为1号的所有排列相邻元素的差为N的最高金额的PermutationSum。
Given an integer N. We need to find out the PermutationSum where PermutationSum for integer N is defined as the maximum sum of difference of adjacent elements in all arrangement of numbers from 1 to N.
举例设N = 3，那么答案是3
Example Let N=3 then answer is 3
说明：对于N = 3，可能的安排是：
Explanation : For N=3, possible arrangements are :
{1,2,3}
{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}
{3,2,1}
PermutationSum的价值排列{1,2,3}为2，即ABS（1-2）+ ABS（2-3）= 2
Value of PermutationSum for arrangement {1,2,3} is 2 i.e abs(1-2)+abs(2-3)=2
PermutationSum的价值排列{1,3,2}为3。
Value of PermutationSum for arrangement {1,3,2} is 3.
PermutationSum的价值排列{2,1,3}为3。
Value of PermutationSum for arrangement {2,1,3} is 3.
PermutationSum的价值排列{2,3,1}为3。
Value of PermutationSum for arrangement {2,3,1} is 3.
PermutationSum的价值排列{3,1,2}为3。
Value of PermutationSum for arrangement {3,1,2} is 3.
PermutationSum的价值排列{3,2,1}为2。
Value of PermutationSum for arrangement {3,2,1} is 2.
所以PermutationSum的所有安排的最大值为3。
So the maximum value of PermutationSum for all arrangements is 3.
我们需要找到这个最大值给出n，其中n是高达100000。
We need to find this maximum value for given N where N is upto 100000.
我有N个！解。但它不会对大的N工作。
I have N! solution. But it won't work for large N.
推荐答案
格雷厄姆Cormode给出 A047838 的解决方案：答案是完全地板（N ^ 2/2 - 1）。
Graham Cormode gives a solution in A047838: the answer is exactly floor(N^2/2 - 1).
这篇关于最大化相邻元件的差的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！