First and Second Highest sum from unsorted Array in Java

Finding the highest and second highest sum from unsorted array in Java is one of the frequently asked question in most of the interviews. They can also ask to write only for finding the highest value sum from unsorted array with single iteration. I am not going to explain more of theory, let’s have a look at below programs.
 
Before going into the first and second highest sum, let’s find highest sum. The below source code will help you to find the same.
package com.ds.practice;

public class HighestSum1 {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Hold highest two values from array
int first = 0, second = 0;
for (int i = 0; i < ar.length; i++) {
// check the value is greater than first
// if yes, assign first to second and hold new value in first
if (ar[i] > first) {
second = first;
first = ar[i];
}
}

System.out.println(first + second);
}
}

The below source code is the another way of finding the highest sum from an unsorted array in java. This way will help you to find second highest sum from given unsorted array in java.

package com.ds.practice;

public class HighestSum {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Parameters to hold two highest values from array
int first, second;

//if array has only 1 element
if (ar.length < 2) {
System.out.println(ar[0]);
}
//if array has only 2 elements
else if (ar.length < 3) {
System.out.println(ar[0] + ar[1]);
}
//if array has more than 2 elements
else {

// take first 2 elements into first and second
if (ar[0] > ar[1]) {
first = ar[0];
second = ar[1];
} else {
first = ar[1];
second = ar[0];
}

//loop remaining elements in array and change first and second values based on value
for (int i = 2; i < ar.length; i++) {
if (ar[i] > first) {
second = first;
first = ar[i];
} else if (ar[i] > second && ar[i] != first) {
second = ar[i];
}
}

//Printing final highest sum
System.out.println(first + second);
}
}
}

Now, we will enter into the actual problem. The below source will help you how to find highest and second highest sum from given unsorted array in java.

package com.ds.practice;

public class MaxFirstSecondSum {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Parameters to hold highest 3 values from array
int first = 0, second = 0, third = 0;
// if array has only 1 element
if (ar.length < 2) {
System.out.println(ar[0]);
}
// if array has only 2 elements
else if (ar.length < 3) {
third = ar[0] > ar[1] ? ar[0] : ar[1];
System.out.println(ar[0] + ar[1] + " " + third);
}
// if array has more than 2 elements
else {
// Holding first two elements from array
if (ar[0] > ar[1]) {
first = ar[0];
second = ar[1];
} else {
first = ar[1];
second = ar[0];
}
// Actual logic to find top 3 elements from array
for (int i = 2; i < ar.length; i++) {
if (ar[i] > first) {
third = second;
second = first;
first = ar[i];
} else if (ar[i] > second && ar[i] != first) {
third = second;
second = ar[i];
}
}
System.out.println((first + second) + " " + (second + third));
}
}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s