在此问题中,我们得到了一个范围为[1,n]的n个整数的数组。我们的任务是创建一个程序,该程序将找到| arr [0] – arr [1]-+ | arr [1] – arr [2]-+…+ | arr [n – 2] – arr [ n – 1]。
让我们举个例子来了解这个问题,
输入-数组= {1,2,3}
输出-3
说明-
max sum is |1-3|+|2-1| = 3
为了解决这个问题,一种简单的方法是从数组创建所有排列。并从置换中找到所有值的最大值。一种更有效的方法是将n的每个值的所有最大值归一化,然后创建一个通用公式。
所以,
Maximum sum for (n = 1) = 0 Maximum sum for (n = 2) = 1 Maximum sum for (n = 3) = 3 Maximum sum for (n = 4) = 7 Maximum sum for (n = 5) = 11 So, the maximum value is 0, 1, 3, 7, 11…
通式为((n * n / 2)-1)
该程序说明了我们解决方案的工作原理,
#include <iostream> using namespace std; int maxAbsVal(int n) { if (n == 1) return 0; return ((n*n/2) - 1); } int main() { int n = 4; cout<<"The maximum sum of absolute difference is "<<maxAbsVal(n); return 0; }
输出结果
The maximum sum of absolute difference is 7