最大化相邻元件的差的总和 [英] Maximise the sum of difference of adjacent elements

问题描述

给定一个整数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).

这篇关于最大化相邻元件的差的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！