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:

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

  2. 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:

  1. 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.

  2. Repeat this process for all such sub-arrays with length L and R and return the maximum possible value found.

  3. 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:

  1. 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.

  2. 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.

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

    • L comes before R.
    • R comes before L.
  4. 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.

  5. 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.

  6. 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″]

Previous post
Next post Array ZigZag

Leave a Reply

Your email address will not be published. Required fields are marked *