Help me in solving MAXADJSUM problem

help
,
1

My issue

My code worked for the example cases when i ran it on IntelliJ but on editor of Codechef it keeps printing the 2nd case as 24 when it should be 15 and it is

My code

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc = new Scanner(System.in);
	    int t = sc.nextInt();
	    int insum = 0;
	    int finalsum = 0;
	    
	    for(int i = 0 ; i < t ; i++){
	        int n = sc.nextInt();
	        int[] a = new int[n];
	        
	        for(int j = 0;j<n;j++){
	           a[j]=sc.nextInt(); 
	        }
	        Arrays.sort(a);
	        
	        for(int k = n - 1 ; k > 0;k--){
	            insum = 0 ;
	            insum =  a[k] + a[k - 1];
	            finalsum += insum;
	        } 
	        
	        System.out.println(finalsum);
	        
	    }
	    

	}
}

Problem Link: Maximise Adjacent Sum Practice Coding Problem - CodeChef

2

Hey Buddy,
Checkout my code

import java.util.;
import java.lang.;
import java.io.*;

class Codechef
{
public static void main (String args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0){
int n = sc.nextInt();
int arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
int temp = arr[1];
arr[1] = arr[n-1];
arr[n-1] = temp;
int sum = 0;
for(int i=0;i<n-1;i++){
int adj_sum = arr[i]+arr[i+1];
sum += adj_sum;
}
System.out.println(sum);
t–;
}

}

}

1 Like
3

What you are doing is only summing up all the elements in the array, which is not what the problem is asking you.

The problem is asking you to maximize the sum rearranging the array in any way you need.

Say, imagine I send the following array to your code:
[4,5,1,2,3]

  1. Your code only sorts it. Leting it be:
    [1,2,3,4,5]

  2. The you sum the elements backwards:
    (5+4) + (4+3)+(3+2)+(2+1)

  3. Giving you 24 as output. But that is not the maximum possible sum. It is 27
    That is:
    [2,3,4,5,1]
    (2+3)+(3+4)+(4+5)+(5+1) = 27

Despide the array, what you are ask to do is this:
A = [a1,a2, a3, a4]

sum = (a1+a2)+(a2+a3)+(a3+a4) = a1 + 2(a2+a3) + a4

If you want to maximize the sum, you should let the biggers being multiplied by 2, and the smallest in the edges.

You got the right idea sorting the array, let me change something:

    Arrays.sort(a);
    int[] finalArray = new int[n];

    for(int k=1; k<n; k++){
        finalArray[k-1] = a[k];
    } 
    finalArray[n-1] = a[0];

    finalsum = 0;
    for (int k=0; k<n-1; k++) {
        finalsum += finalArray[k] + finalArray[k+1];
    } 

    System.out.println(finalsum);

Guess why.

1 Like
4

You shifted the elements to the left so as to get the biggest elements to be multiplied by 2. Thank you for taking the time to explain it

1 Like