给定一个数组，我们需要修改该数组的值，使两个连续元素之间的绝对差之和最大化。如果数组元素的值是X，那么我们可以将其更改为1或X。 例如：
null
Input : arr[] = [3, 2, 1, 4, 5]Output : 8We can modify above array as,Modified arr[] = [3, 1, 1, 4, 1]Sum of differences = |1-3| + |1-1| + |4-1| + |1-4| = 8Which 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时，才使用前i个元素存储和的最大值；如果第i个数组值本身保持为[i]，则dp[i][1]存储使用前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 ] = 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. ?> |
Javascript
<script> // Javascript 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. let dp = new Array(N); for (let i = 0; i < N; i++) { dp[i] = new Array(2); for (let j = 0; j < 2; j++) { dp[i][j] = 0; } } for (let i = 0; i < N; i++) dp[i][0] = dp[i][1] = 0; for (let 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]); } let arr = [3, 2, 1, 4, 5]; let N = arr.length; document.write( maximumDifferenceSum(arr, N)); // This code is contributed by rameshtravel07. </script> |
输出
8
输出：
8
时间复杂性： O（N） 辅助空间： O（N） 本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
另一种方法 :
说明： 为了随时计算答案，只需要以前的状态值。因此，我们不需要使用整个DP数组，只需要使用两个变量prev_change和prev_nochange，就可以降低空间复杂度。
Python3
def maximumDifferenceSum(arr, n): prev_change, prev_nochange = 0 , 0 for i in range ( 1 ,n): change = max (prev_change , arr[i - 1 ] - 1 + prev_nochange) nochange = max (prev_nochange + abs (arr[i] - arr[i - 1 ]) , arr[i] - 1 + prev_change) prev_change = change prev_nochange = nochange return max (prev_change, prev_nochange) if __name__ = = '__main__' : arr = [ 3 , 2 , 1 , 4 , 5 ] N = len (arr) print (maximumDifferenceSum(arr, N)) |
输出
8
时间复杂性 ：O（N）
辅助空间 ：O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
