修改数组以最大化相邻差异的总和 _数据结构

本文概述

C ++
Java
Python3
C#
的PHP

给定一个数组, 我们需要以使两个连续元素之间的绝对差之和最大的方式修改此数组的值。如果数组元素的值为X, 则可以将其更改为1或X。
例子：

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

这个问题是装配线调度可以使用动态编程解决。我们需要最大化差异总和, 每个值X都应更改为1或X。为达到上述条件, 我们采用了一个数组长度为2列的dp数组, 其中dp [i] [0]存储的最大值仅当第i个数组的值修改为1且dp [i] [1]存储第i个元素的和的最大值(如果第i个数组的值保留为a [i]本身时)。 ,
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 ] = 0for 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# 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. ?>

输出：