C ++中相邻元素之差的最大和

在这个问题中，给我们一个数字N。我们的任务是创建一个程序，以查找C ++中相邻元素之差的最大和。

问题描述

我们将找到所有置换数组的相邻元素之间的绝对差的最大和。

让我们举个例子来了解这个问题，

输入值

N = 4

输出结果

7

说明

All permutations of size 4 are :
{1, 2, 3, 4} = 1 + 1 + 1 = 3
{1, 2, 4, 3} = 1 + 2 + 1 = 4
{1, 3, 2, 4} = 2 + 1 + 2 = 5
{1, 3, 4, 2} = 2 + 1 + 2 = 5
{1, 4, 2, 3} = 3 + 2 + 1 = 6
{1, 4, 3, 2} = 3 + 1 + 1 = 5
{2, 1, 3, 4} = 1 + 2 + 1 = 4
{2, 1, 4, 3} = 1 + 3 + 1 = 5
{2, 3, 1, 4} = 1 + 2 + 3 = 6
{2, 3, 4, 1} = 1 + 1 + 3 = 5
{2, 4, 1, 3} = 2 + 3 + 2 = 7
{2, 4, 3, 1} = 2 + 1 + 2 = 5
{3, 1, 2, 4} = 2 + 1 + 2 = 5
{3, 1, 4, 2} = 2 + 3 + 2 = 7
{3, 2, 1, 4} = 1 + 1 + 3 = 5
{3, 2, 4, 1} = 1 + 2 + 3 = 6
{3, 4, 1, 2} = 1 + 3 + 1 = 5
{3, 4, 2, 1} = 1 + 2 + 1 = 4
{4, 1, 2, 3} = 3 + 1 + 1 = 5
{4, 1, 3, 2} = 3 + 2 + 1 = 6
{4, 2, 1, 3} = 2 + 1 + 2 = 5
{4, 2, 3, 1} = 2 + 1 + 2 = 5
{4, 3, 1, 2} = 1 + 2 + 1 = 4
{4, 3, 2, 1} = 1 + 1 + 1 = 3

解决方法

为了解决这类问题，我们需要找到置换的总和。

这里是N的不同值的相邻元素的最大差之和的一些值。

N = 2, maxSum = 1
N = 3, maxSum = 3
N = 4, maxSum = 7
N = 5, maxSum = 11
N = 6, maxSum = 17
N = 7, maxSum = 23
N = 8, maxSum = 31

这个和看起来像是N的加法+ N个词的和

maxSum = S(N)+ F(N)S(N)= n(n-1)/ 2，而F(N)是N的未知函数

让我们使用S(N)，maxSum(N)找到F(N)。

F(2) = 0
F(3) = 0
F(4) = 1
F(5) = 1
F(6) = 2
F(7) = 2
F(8) = 3

从这里，我们可以得出F(N)是Int（N / 2-1）。F(N)每N的第二个值增加一次，最初对于2和3则为零。

这样就可以得出maxSum的公式，

maxSum = N(N-1)/2 + N/2 - 1
maxSum = N(N-1)/2 + N/2 - 2/2
maxSum = ( N(N-1) + N - 2 )/2
maxSum = ( (N^2) - N + N - 2 )/2
maxSum = ((N^2) - 2 )/2

使用此公式，我们可以找到任何给定N值的maxSum值。

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int calcMaxSumofDiff(int N){
   int maxSum = 0;
   maxSum = ((N*N) - 2) /2 ;
   return maxSum;
}
int main(){
   int N = 13;
   cout<<"The maximum sum of difference of adjacent elements is "<<calcMaxSumofDiff(N);
   return 0;
}

输出结果

The maximum sum of difference of adjacent elements is 83