Maximize the sum by selecting a Subsequence

By
Sohaib
-
0
7
Adv1


Adv2

Enhance Article

Save Article

Like Article

Enhance Article

Save Article

Given an array X[] of size N together with an integer Ok. Then the duty is to decide on a sub-sequence to maximize the sum by deciding on the beginning index i 
(1 ≤ i ≤ N ) and make the subsequence of all the weather, that are at a steady distance (i + Ok) until we aren’t out of the array X[] or on the final index. 

Examples:

Enter: N = 5, Ok = 2, X[] = {2, 5, 5, 8, 2}
Output: 13
Rationalization: The operation is carried out as: 

  • Let choose index i = 2 and then A2 = 5 In order that subsequent aspect at Okth distance from i = (i + Ok) = (2+2) = 4, A4 = 8, Now if we leap extra subsequent Okth index, formally (4 + 2) = 6. So it doesn’t exist or we’re out of the X[]. So the subsequence turns into = {5, 8}, Which provides sum as 13. Which is most doable. 

Enter: N = 4, Ok = 4, X[] = {1, 4, 5, 50}
Output: 50
Rationalization: It is going to be optimum to decide on i = 4 then A4 = 50. So the subsequence turns into {50}. Now, subsequent (i+Okth) index doesn’t exist. Due to this fact the subsequence has sum as 50. Which is most doable. It may be verified that no sum greater than 50 is feasible utilizing the given operation.

Strategy: Implement the thought under to unravel the issue

The issue is Grasping logic based mostly and may be solved utilizing the observations. 

Steps have been taken to unravel the issue:

  • Create an array of size N let’s say Y[].
  • Create a variable let’s say max and initialize it to a minimal integer worth for storing the utmost doable sum.
  • Run a loop from i = N-1 to i ≥ 0 and observe the below-mentioned steps below the scope of the loop:
    • Y[i] = i + Ok < N ? X[i] + Y[i + K] : X[i]
  • Now simply discover the utmost worth from Y[] by traversing it and updating the max
  • Output the worth of max.

Beneath is the code to implement the strategy:

Java

  

public class Most important {

  

    

    public static void fundamental(String[] args)

    {

  

        

        int N = 5;

        int Ok = 2;

        int X[] = { 2, 5, 5, 8, 2 };

  

        

        MaxSubsequenceSum(N, Ok, X);

    }

  

    

    

    static void MaxSubsequenceSum(int N, int Ok, int[] X)

    {

        int l = Integer.MIN_VALUE;

  

        

        int Y[] = new int[N];

  

        

        

        int max = Integer.MIN_VALUE;

  

        

        

        for (int i = N - 1; i >= 0; i--) {

            Y[i] = i + Ok < N ? X[i] + Y[i + K] : X[i];

        }

  

        

        for (int i = 0; i < N; i++) {

            max = Math.max(Y[i], max);

        }

  

        

        System.out.println(max);

    }

}

Time Complexity: O(N)
Auxiliary House: O(N)

Adv3