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

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

本文概述

给定一个数组, 我们需要以使两个连续元素之间的绝对差之和最大的方式修改此数组的值。如果数组元素的值为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 ] = 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

时间复杂度：O(n)

辅助空间：O(n)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: