# Maximum Average Sum of Two Subsequences of Array

**Problem statement:** Write a program to find the maximum sum of the average of two subsequences of the array of integer types.

**Example:** Let’s take an example.

Given array: [50, 40, 30, 20]

Output: 80.

Explanation:

We can create two subsequences in different ways.

**Case 1: **

Subsequences are [50, 40] and [30, 10].

The average of the first subsequence is (50+40)/2=45.

The average of the second subsequence is (30+20)/2=25.

The sum of the two averages is 45+25=**70**.

**Case 2: **

Subsequences are [50] and [40, 30, 10].

The average of the first subsequence is (50)/1=50.

The average of the second subsequence is (40+30+20)/3=30.

The sum of the two averages is 45+25=**80**.

There are a few more ways/cases to create the subsequence. But the maximum sum of two subsequences will **80**.

Now let’s write a program to solve this coding challenge. You can use any programming language of your choice (like C++, Java, Python, etc) to solve this challenge.

#### Python Program

**Prerequisite:**

**Code:**

input = [50, 40, 30, 20] nA = 1 avgA = input[0] nB = 0 avgB=0 for i in input[1:]: newAvgA = (nA*avgA + i)/(nA+1) newAvgB = (nB*avgB + i)/(nB+1) if (newAvgA + avgB) > (newAvgB + avgA): nA=nA+1 avgA=newAvgA else: nB=nB+1 avgB=newAvgB print(avgA+avgB)

**Output:**

80.0

You can try with the different input array (list in the case of Python).

Write a program in other programming languages and share it with us in the comment section below.

#### Complexity

As we are traversing each element in the array/list only once, the time complexity of this algorithm is `O(n)`

. Where ‘n’ is the size of the array.

This coding challenge to get the maximum average sum of two sub-arrays has been asked in many coding interviews of product-based companies.