ผลรวมสูงสุดของความแตกต่างขององค์ประกอบที่อยู่ติดกันใน 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

หา F(N) โดยใช้ S(N), maxSum(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

เมื่อใช้สูตรนี้ เราสามารถหาค่า maxSum ของค่าที่กำหนดของ N

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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