Crea sito

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:

  1. Notebook (30$)
  2. Smartphone (10$)
  3. TV (15$)
  4. 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 🙂