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つおきに増加​​し、最初は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