Tutorialspoint.dev

Modify array to maximize sum of adjacent differences

Given an array, we need to modify values of this array in such a way that sum of absolute differences between two consecutive elements is maximized. If the value of an array element is X, then we can change it to either 1 or X.
Examples :

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


This problem is a variation of Assembly Line Scheduling and can be solved using dynamic programming. We need to maximize sum of differences each value X should be changed to either 1 or X. To achieve above stated condition we take a dp array of array length size with 2 columns, where dp[i][0] stores the maximum value of sum using first i elements only if ith array value is modified to 1 and dp[i][1] stores the maximum value of sum using first i elements if ith array value is kept as a[i] itself.Main thing to observe is,

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.
?>


Output :

8

Time Complexity : O(N)
Auxiliary Space : O(N)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter