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

Question

Candy Love

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

1. 每个 child 至少应该得到一颗糖果。
2. 最多可以给第 i 个 child 的糖果为 A[i]。

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

函数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.

Answer 1

-为了最大化差值之和，数组的每个值 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)); 

    } 
}