CODEWITHSUNDEEP
javaarrays
Sandeep Verma
Sandeep Verma

Reputation: 1

How to create a new Array from Original Array in which the sum of all differences is maximum?

Candy Love

There are N children coming to the party and you have decided to distribute candies as return gift to those children. Children are numbered from 1 to N. You are given an array A which defines the maximum number of candies which can be given to any child. There are restrictions on number of candies which can be given to any child :

  1. Each child should be given at least one candy.
  2. The maximum candies which can be given to ith child is A[i].

The collective success of party is given by a function S which is calculated as follows :

function S():

Array C denotes the number of candies given to each child 
   sum = o 
   for i = 2 to N: 
       sum = sum a abs(c[i]-[i-1]) 
   return sum

Now as the host of party you want to maximize the success of party. So distribute the candies in such a way which maximizes the success of party. Output the maximum value of success which can be obtained.

>##Sample Input##
You will be given N denoting the number of children in party and next line will consist of N space separated integers denoting the maximum candies which can be given to any child.


>##Sample Output##
Print the maximum success value of party which can be obtained. 


>##Constraints##
2 <= N <= 10^5
1 <= A[i] <= 10^9


>##Sample Input 1##
3
1 2 4


>##Sample Output 1##
3


>##Sample Input 2##
6
3 10 15 10 3 10


>##Sample Output 2##
45


>##Explanation 1##
One of the ways to get success value as 3 is giving {1,2,4} candies to children respectively.

>##Explanation 2##
One of the ways to get success value as 45 is giving {1,10,1,10,1,10} candies to children respectively.

Upvotes: 0

Views: 335

Answers (1)

Vasi G.
Vasi G.

Reputation: 171

-to maximize the sum of differences each value X of the array should be changed to either 1 or X

import java.io.*; 

class Test  
{ 
    static int maximumDifferenceSum(int arr[], int N) 
    { 
        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++) 
        { 
            //dp[i][0] stores the maximum value of sum using first i elements if ith array value is modified to 1
            dp[i + 1][0] = Math.max(dp[i][0], 
                           dp[i][1] + Math.abs(1 - arr[i])); 

            //dp[i][1] stores the maximum value of sum using first i elements if ith array value is kept as a[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]); 
    } 

    public static void main (String[] args)  
    { 
        int arr[] = {3,10,15,10,3,10}; 
        int N = arr.length; 

        // output will be 45
        System.out.println( maximumDifferenceSum(arr, N)); 

    } 
}

Upvotes: 1

Related Questions