数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于: 2020-10-15
202 次浏览
广告