# How to find the maximal sum in Array in Java

**INTRODUCTION TO THE ALGORITHMIC PROBLEM:**

Imagine that you receive a 50$ gift card which can be used in a famous shop of your town. You can use this gift card to buy only two items and the sum of their prices must be lower than 50$.

This shop has a lot of products and you want to know what is the best combination in order to buy two product with the maximal sum lower than 50$. For example, there are 3 items:

- Notebook (30$)
- Smartphone (10$)
- TV (15$)
- Fridge (45$)

If you want to use the gift card’s dollars as much as you can, what is the best combination with a sum lower than 50$? Obviously is:

Notebook (30$) + TV (15$) = 45$ < 50$ (You only loose 5$)

But if you choose:

Notebook (30$) + Smartphone (10$) = 40$ < 50$ (Valid, but you loose 10$)

Or

Fride (45$) + TV (15$) = 60$ > 50$ (You can’t use the gift card 🙁 )

Your choice would not be efficient.

**IDEA FOR AN ALGORITHMIC SOLUTION:**

The idea of this algorithm is to create an Array with some numbers (which represents the prices of the products) and then sort with a normal Sorting Algorithm like QuickSort or MergeSort.

When the Array is sorted, the algorithm will use a nested loop (composed by 2 for loops) in which there is an if that says:

*If the sum of the Price of I plus the Price of J is lower than 50$ AND this sum is greather than the max sum obtained within this loop (that initially is set to 0), then the MaximalSum will be the sum of J + I.*

At the end the algorithm will return the maximal sum obtained.

**SOLUTION WRITTEN IN JAVA:**

This is the working snippet in Java that returns the maximal sum according to the idea written before.

/* * Code written by Big O Notation (bigonotation.altervista.org) * Please press like to our Facebook Page or share this article * if you have found it useful :) */ import java.util.Arrays; public class Main { public static void main(String[] args) { int[] A = { 7, 12, 17, 2, 9, 4 }; Main m = new Main(); System.out.println("Maximal sum: " + m.maximalSum(A, 14)); } public int maximalSum(int[] Array, int value) { Arrays.sort(Array); int max = 0; int i = 0; int j = 0; for(i = 0; i < Array.length - 1; i++) { for(j = i+1; j < Array.length; j++) { if((Array[i]+Array[j])<= value && ((Array[i]+Array[j]) > max)) { max = Array[i] + Array[j]; } } } return max; } }

If you like this article comment it and share on Facebook and other Social.

I would also be very happy if you like the Big O Notation’s Facebook Page.

Bye 🙂