Power of Santa - CodeChef Solution in Java | AskTheCode

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;		
	}
}
16 views0 comments

Recent Posts

See All

Golf CodeChef Solution in Java - AskTheCode

CodeChef May Long Challenge Solution | Golf (LKDNGOLF) solution | AskTheCode Golf (LKDNGOLF) solution Problem: It's a lockdown. You’re bored in your house and are playing golf in the hallway. The hall

Solubility - CodeChef Solution in Java and C++| AskTheCode

CodeChef May Long Challenge Solution | Solubility (SOLBLTY) solution | AskTheCode Solubility (SOLBLTY) solution Problem: Suppose for a unit rise in temperature, the solubility of sugar in water increa

Valid Paths CodeChef Solution in C++ | AskTheCode

CodeChef May Long Challenge Solution | Valid Paths (VPATH) solution | AskTheCode Valid Paths (VPATH) CodeChef solution Problem: You are given a tree with N nodes numbered from 1 to N. A set S of nodes