CodeChef Dynamic Programming Practice Solution | Power of Santa solution in Java | AskTheCode
Problem:
You are given an array of candies (Arr) of size N. The power of the Santa represents the sum of the values that you obtain after performing the described operations for N times. Your task is to delete the array by performing the following operations:
For any turn(i) where (1 <= i <= N), delete either of the end (first or last) elements of remaining array.
Before deleting that element (let's say at index K), it contributes to the sum of the values as Arr[K] x turn(i) + SV(i) the power of the array. Here, turn(i) represents the number of turns in which you are performing the operation.
SV(i) represents the value of the maximum element that is present in the remaining array before the ith turn is performed.
You are required to perform this in such a way that you maximize the value of the power of the Santa.
You must print the maximum value of the power that can be obtained after the array is completely deleted.
Input:
First line contain N i.e., length of Array
Second line contains N space separated integers denoting the elements of the array.
Output:
Print in a new line the value that represents the maximum power that can be obtained after the array is completely deleted.
Constraint:
1 <= N <= 10^3 1 <= Arr(i) <= 10^9
Example Input:
5
5 4 3 6 2
Example Output:
96
Code:
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef{
public static void main (String[] args) throws java.lang.Exception{
try {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int Arr[] = new int[N];
for (int i = 0; i < N; i++)
Arr[i] = sc.nextInt();
System.out.println(add(Arr,0, N-1, 1, N));
}catch (Exception e) {
}
}
static int add(int arr[], int lb, int ub, int l, int size) {
if (l > size || lb > ub)
return 0;
int max = -1;
for(int j = lb; j <= ub; j++)
max=Math.max(max, arr[j]);
return Math.max(add(arr, lb+1, ub, l+1, size)+arr[lb]*l, add(arr, lb, ub-1, l+1, size)+arr[ub]*l)+max;
}
}
Comentarios