时间戳

首页 > 解决方案 > 如何从原始数组创建一个新数组，其中所有差异的总和最大？

java - 如何从原始数组创建一个新数组，其中所有差异的总和最大？

问题描述

糖果之恋

有 N 个孩子来参加聚会，您决定向这些孩子分发糖果作为回礼。孩子的编号从 1 到 N。给你一个数组 A，它定义了可以给任何孩子的糖果的最大数量。可以给任何孩子的糖果数量是有限制的：

  1. 应该给每个孩子至少一颗糖果。
  2. 可以给第 i 个孩子的最大糖果是 A[i]。

党的集体成功由函数 S 给出，计算如下：

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

现在，作为派对的主持人，您希望最大限度地提高派对的成功率。因此，以最大限度地提高派对成功的方式分发糖果。输出可以得到的最大成功值。

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

标签： javaarrays

解决方案

- 为了最大化差值的总和，数组的每个值 X 应更改为 1 或 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)); 

    } 
}

推荐阅读