Finding the largest sum possible

Question

I have some work which needs to deal with adding numbers together from two arrays. For example, if the input is like this:

array1
202 167 178 18
array2
467 15 98 3

The program would pair them together, in which case the larger number overrides the smaller number, making them irrelevant. Then it adds up all the large numbers to get a sum. I had already solved how to find the smallest sum, but the largest sum seems a lot harder to do. As the example above, the result would be

467+202+167+178=1014

Since they are the four largest numbers.(Pair 467 with 18, and 202/167/178 with any of the rest)
I thought about something like

for(int n=numberofnumbers-1;n>n/2;n-=1)
{
     if(array1[n]>=array2[n])
     {
         anotherarray[n]=array1[n];
     }
     else
     {
         anotherarray[n]=array2[n];
     }
}

But it would use one number more than once and the output would be incorrect. I need some help on how I can make it work the way I wanted.

Edit:desired input:

array1
202 167 178 18
array2
467 15 98 3

desired output:

1014

What I got with my not-working program:

1338

Edit 2: The numbers are sorted from another method.

Edit 3: After looking at some suggestions, I came up with this:

private int[] sorting(int[] dspeed,int[] pspeed)
{
int[] answer=new int[dspeed.length+pspeed.length];
int i=0, j=0, k=0;
while(i<dspeed.length&&j<pspeed.length)
    answer[k++]=dspeed[i]<pspeed[j] ? dspeed[i++] : pspeed[j++];

while(i<dspeed.length)
    answer[k++]=dspeed[i++];

while(j<pspeed.length)
    answer[k++]=pspeed[j++];

return answer;

}

supposing array1 is dspeed and array2 is pspeed, along with

        final int[] ddspeed=sorting(dspeed, pspeed);
        int answer=0;
        for(int x=length-1;x>length/2;x--)
        {
            answer+=ddspeed[x];
        }
        System.out.println(answer);  
        break;

However, I would get answers that makes no sense. example input:

array1
1 2
array2
1 2

output

0

Answer 1

Juust another aproach: Sort both arrays. Compare the greatest number from both arrays and take it for the sum. Go on with this without the choosen element till you have your pairs.

sum_max=0;
Arrays.sort(arr1);
Arrays.sort(arr2);
n1=array1.length-1;
n2=n1;
count=n1;

while(count>=0)
{
    if(array1[n1]>=array2[n2])
     {
         n_max=array1[n1];
         n1--;
     }
     else
     {
         n_max=array2[n2];
         n2--;
     }
     sum_max += n_max;
     count--;
}

Answer 2

The simplest way to do this is to merge the two arrays, sort the array, and then add the last four elements of the array. Obviously, there are better ways to do this but since I am sticking with the simplest that you can understand. Like this:

import java.util.Arrays;

class Main {
  public static void main(String[] args) {
        int[] arr1 = { 202, 167, 178, 18 };
        int[] arr2 = { 467, 15, 98, 3 };
        int[] arr3 = new int[arr1.length+arr2.length];

        for(int i=0;i<arr1.length;i++)
            arr3[i]=arr1[i];

        for(int i=0;i<arr2.length;i++)
            arr3[arr1.length+i]=arr2[i];

        Arrays.sort(arr3);

        int len = arr3.length;

        int sum = arr3[len-1]+ arr3[len-2]+ arr3[len-3]+ arr3[len-4];
        System.out.println(sum);
  }
}

You get the idea and you can modify it as per your requirement.

Answer 3

If I understand right, the rules are as follows:

• Pair up a number from array 1 with a number from array 2
• Numbers can only be paired once
• Choose largest number from each pair
• Sum those numbers
• Find combination of pairs with largest sum

That means you'd want to sum using largest numbers from each array. Easiest way to do that is to sort both arrays, one ascending and one descending. Now pair up by index position.

Sorting an array of primitives ascending is easy in Java. Just use Arrays.sort().

There is no method for sorting descending, so you could sort ascending and reverse the array, but there is no method for that either, though it's easy to write a method for that.

We'll just pair up the numbers in reverse order.

private static int highestSum(int[] array1, int[] array2) {
    if (array1.length != array2.length)
        throw new IllegalArgumentException();
    Arrays.sort(array1);
    Arrays.sort(array2);
    int sum = 0;
    for (int i = 0; i < array1.length; i++) {
        int value1 = array1[i];
        int value2 = array2[array2.length - i - 1];
        int max = Math.max(value1, value2);
        sum += max;
    }
    return sum;
}

Test

System.out.println(highestSum(new int[] { 202, 167, 178, 18, },
                              new int[] { 467, 15, 98, 3, }));

Output

1014

Answer 4

Look at this code:

sum_max=0;
for(int n=0; n<array1.length; n++)
{
     if(array1[n]>=array2[n])
     {
         n_max=array1[n];
     }
     else
     {
         n_max=array2[n];
     }
     sum_max += n_max;
 }

Even I actually not tested it, I think it should do what you want.

Or if you want it a little bit shorter:

sum_max=0;
for(int n=0; n<array1.length; n++)
{
     n_max = (array1[n]>=array2[n]) ? array1[n] : array2[n];
     sum_max += n_max;
}