# Wealthy Father

#### CONCEPTS USED:

Sliding Window Technique

#### DIFFICULTY LEVEL:

Medium

#### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given an array

`A`

, we need to find two sub-arrays with specific lengths`L`

and`R`

such that sum of these sub-arrays is`Maximum`

among all possible choices of sub-arrays and these sub-arrays don’t overlap each other.

**See original problem statement here**

**NOTE**:

Both sub-arrays should be continuous and should not contain same element.

Sub-array L can come after or before sub-array R.

#### For Example:

```
Input : A = [6, 3, 5, 2, 6, 8, 9]
L = 3, R = 2
Output : 32
Explanation: There can be many possible sub-arrays -
[6, 3, 5] [2, 6]
[6, 3, 5] [6, 8]
[6, 3, 5] [8, 9]
[3, 5, 2] [6, 8]
[3, 5, 2] [8, 9]
[5, 2, 6] [6, 3]
[5, 2, 6] [8, 9]
[2, 6, 8] [6, 3]
[2, 6, 8] [3, 5]
[6, 8, 9] [6, 3] --> It gives us maximum value = 32
[6, 8, 9] [3, 5]
[6, 8, 9] [5, 2]
```

#### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

The simple solution would be to first traverse a sub-array for

`L`

elements and look for another sub-array with`R`

elements from the remaining elements in the array ,take out their`Sum`

and compare it with the initial max value.Repeat this process for all such sub-arrays with length

`L`

and`R`

and return the maximum possible value found.

`Time Complexity`

of this solution will be`O(N^2)`

according to data structures and algorithms in c++.

**EXAMPLE**:

**Step 1**

**Step 2**

**Step 3**

**Step 4**

**Step 5**

#### EFFICIENT METHOD:

The idea is to use

`Sliding Window Technique`

, where we create a window of`(L+R)`

elements initially and keep processing all such windows present in the array.Assume initialize variables

`Result`

as sum of first window of size`(L+R)`

,`lmax`

as sum of first`L`

elements and`rmax`

as sum of first`R`

elements.Now move to the next window, we have two cases :

`L`

comes before`R`

.`R`

comes before`L`

.When

`L`

comes before`R`

, we will find the sum of starting`L`

elements of the current window as`current left`

and compare it with our`lmax`

value, the higher of the two will be stored in`lmax`

, similarly calculate the sum of`R`

elements as`current right`

, and compare the current`lmax`

+`current right`

with`Result`

and store the maximum of two in the`Result`

.When

`R`

comes before`L`

, we will find the sum of starting`R`

elements of the current window as`current right`

and compare it with our`rmax`

value, the higher of the two will be stored in`rmax`

, similarly calculate the sum of`L`

elements as`current left`

, and compare the current`rmax`

+`current left`

with`Result`

and store the maximum of two in the`Result`

.Similarly all such windows are processed from

`i= (left+right)`

to`i<N`

.

**NOTE**: For finding the sum of ranges of array elements quickly, `Prefix Sum Array`

can be used, which gives us the sum of any range of elements in an array in `O(1)`

`Time Complexity`

.

** Illustration of Prefix Sum Array**:

```
A[] = [1, 2, 3, 4, 5]
Prefix[] = [1, 3, 6, 10, 15]
where Prefix[index] gives us the sum of array till i = index.
Prefix[3] = 10
Sum of elements in range [left, right] = Prefix[right] - Prefix[left-1]
sum [2, 4] = Prefix[4] - Prefix[2-1]
= 15 - 3
= 12
```

[TABS_R id=351]

[forminator_quiz id=”285″]