0

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.
Improve this question

1 Answer 1

Reset to default
1

-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)); } }
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.