# 修改数组以最大化相邻差异的总和

2021年5月3日17:11:05 发表评论 818 次浏览

## 本文概述

``````Input  : arr[] = [3, 2, 1, 4, 5]
Output : 8
We can modify above array as, Modified arr[] = [3, 1, 1, 4, 1]
Sum of differences =
|1-3| + |1-1| + |4-1| + |1-4| = 8
Which is the maximum obtainable value
among all choices of modification.

Input  : arr[] = [1, 8, 9]
Output : 14``````

## C ++

``````// C++ program to get maximum consecutive element
//difference sum
#include <bits/stdc++.h>
using namespace std;

//Returns maximum-difference-sum with array
//modifications allowed.
int maximumDifferenceSum( int arr[], int N)
{
//Initialize dp[][] with 0 values.
int dp[N][2];
for ( int i = 0; i <N; i++)
dp[i][0] = dp[i][1] = 0;

for ( int i=0; i<(N-1); i++)
{
/*  for [i+1][0] (i.e. current modified
value is 1), choose maximum from
dp[i][0] + abs(1 - 1) = dp[i][0] and
dp[i][1] + abs(1 - arr[i])   */
dp[i + 1][0] = max(dp[i][0], dp[i][1] + abs (1-arr[i]));

/*  for [i+1][1] (i.e. current modified value
is arr[i+1]), choose maximum from
dp[i][0] + abs(arr[i+1] - 1)    and
dp[i][1] + abs(arr[i+1] - arr[i])*/
dp[i + 1][1] = max(dp[i][0] + abs (arr[i+1] - 1), dp[i][1] + abs (arr[i+1] - arr[i]));
}

return max(dp[N-1][0], dp[N-1][1]);
}

// Driver code to test above methods
int main()
{
int arr[] = {3, 2, 1, 4, 5};
int N = sizeof (arr) /sizeof (arr[0]);
cout <<maximumDifferenceSum(arr, N) <<endl;
return 0;
}``````

## Java

``````//java program to get maximum consecutive element
//difference sum
import java.io.*;

class GFG
{
//Returns maximum-difference-sum with array
//modifications allowed.
static int maximumDifferenceSum( int arr[], int N)
{
//Initialize dp[][] with 0 values.
int dp[][] = new int [N][ 2 ];

for ( int i = 0 ; i <N; i++)
dp[i][ 0 ] = dp[i][ 1 ] = 0 ;

for ( int i = 0 ; i<(N - 1 ); i++)
{
/* for [i+1][0] (i.e. current modified
value is 1), choose maximum from
dp[i][0] + abs(1 - 1) = dp[i][0] and
dp[i][1] + abs(1 - arr[i]) */
dp[i + 1 ][ 0 ] = Math.max(dp[i][ 0 ], dp[i][ 1 ] + Math.abs( 1 - arr[i]));

/* for [i+1][1] (i.e. current modified value
is arr[i+1]), choose maximum from
dp[i][0] + abs(arr[i+1] - 1) and
dp[i][1] + abs(arr[i+1] - arr[i])*/
dp[i + 1 ][ 1 ] = Math.max(dp[i][ 0 ] +
Math.abs(arr[i + 1 ] - 1 ), dp[i][ 1 ] + Math.abs(arr[i + 1 ]
- arr[i]));
}

return Math.max(dp[N - 1 ][ 0 ], dp[N - 1 ][ 1 ]);
}

//Driver code
public static void main (String[] args)
{
int arr[] = { 3 , 2 , 1 , 4 , 5 };
int N = arr.length;
System.out.println( maximumDifferenceSum(arr, N));

}
}

//This code is contributed by vt_m``````

## Python3

``````# Python3 program to get maximum
# consecutive element difference sum

# Returns maximum-difference-sum
# with array modifications allowed.
def maximumDifferenceSum(arr, N):

# Initialize dp[][] with 0 values.
dp = [[ 0 , 0 ] for i in range (N)]
for i in range (N):
dp[i][ 0 ] = dp[i][ 1 ] = 0

for i in range (N - 1 ):

# for [i+1][0] (i.e. current modified
# value is 1), choose maximum from
# dp[i][0] + abs(1 - 1) = dp[i][0]
# and dp[i][1] + abs(1 - arr[i])
dp[i + 1 ][ 0 ] = max (dp[i][ 0 ], dp[i][ 1 ] +
abs ( 1 - arr[i]))

# for [i+1][1] (i.e. current modified value
# is arr[i+1]), choose maximum from
# dp[i][0] + abs(arr[i+1] - 1) and
# dp[i][1] + abs(arr[i+1] - arr[i])
dp[i + 1 ][ 1 ] = max (dp[i][ 0 ] + abs (arr[i + 1 ] - 1 ), dp[i][ 1 ] + abs (arr[i + 1 ] - arr[i]))

return max (dp[N - 1 ][ 0 ], dp[N - 1 ][ 1 ])

# Driver Code
if __name__ = = '__main__' :
arr = [ 3 , 2 , 1 , 4 , 5 ]
N = len (arr)
print (maximumDifferenceSum(arr, N))

# This code is contributed by PranchalK``````

## C#

``````//C# program to get maximum consecutive element
//difference sum
using System;

class GFG {

//Returns maximum-difference-sum with array
//modifications allowed.
static int maximumDifferenceSum( int []arr, int N)
{

//Initialize dp[][] with 0 values.
int [, ]dp = new int [N, 2];

for ( int i = 0; i <N; i++)
dp[i, 0] = dp[i, 1] = 0;

for ( int i = 0; i <(N - 1); i++)
{
/* for [i+1][0] (i.e. current modified
value is 1), choose maximum from
dp[i][0] + abs(1 - 1) = dp[i][0] and
dp[i][1] + abs(1 - arr[i]) */
dp[i + 1, 0] = Math.Max(dp[i, 0], dp[i, 1] + Math.Abs(1 - arr[i]));

/* for [i+1][1] (i.e. current modified value
is arr[i+1]), choose maximum from
dp[i][0] + abs(arr[i+1] - 1) and
dp[i][1] + abs(arr[i+1] - arr[i])*/
dp[i + 1, 1] = Math.Max(dp[i, 0] +
Math.Abs(arr[i + 1] - 1), dp[i, 1] + Math.Abs(arr[i + 1]
- arr[i]));
}

return Math.Max(dp[N - 1, 0], dp[N - 1, 1]);
}

//Driver code
public static void Main ()
{
int []arr = {3, 2, 1, 4, 5};
int N = arr.Length;

Console.Write( maximumDifferenceSum(arr, N));
}
}

//This code is contributed by nitin mittal.``````

## 的PHP

``````<?php
//PHP program to get maximum
//consecutive element
//difference sum

//Returns maximum-difference-sum
//with array modifications allowed.
function maximumDifferenceSum( \$arr , \$N )
{
//Initialize dp[][]
//with 0 values.
\$dp = array ( array ());
for ( \$i = 0; \$i <\$N ; \$i ++)
\$dp [ \$i ][0] = \$dp [ \$i ][1] = 0;

for ( \$i = 0; \$i <( \$N - 1); \$i ++)
{
/* for [i+1][0] (i.e. current
modified value is 1), choose
maximum from dp[\$i][0] +
abs(1 - 1) = dp[i][0] and
dp[\$i][1] + abs(1 - arr[i]) */
\$dp [ \$i + 1][0] = max( \$dp [ \$i ][0], \$dp [ \$i ][1] +
abs (1 - \$arr [ \$i ]));

/* for [i+1][1] (i.e. current
modified value is arr[i+1]), choose maximum from dp[i][0] +
abs(arr[i+1] - 1) and dp[i][1] +
abs(arr[i+1] - arr[i])*/
\$dp [ \$i + 1][1] = max( \$dp [ \$i ][0] +
abs ( \$arr [ \$i + 1] - 1), \$dp [ \$i ][1] +
abs ( \$arr [ \$i + 1] -
\$arr [ \$i ]));
}

return max( \$dp [ \$N - 1][0], \$dp [ \$N - 1][1]);
}

//Driver Code
\$arr = array (3, 2, 1, 4, 5);
\$N = count ( \$arr );
echo maximumDifferenceSum( \$arr , \$N );

//This code is contributed by anuj_67.
?>``````

``8``