Maximize the sum by selecting a Subsequence

Given an array X[] of size N together with an integer Okay. 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 + Okay) until we’re not out of the array X[] or on the final index. 

Examples:

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

• Let choose index i = 2 and then A₂ = 5 In order that subsequent component at Okay_th distance from i = (i + Okay) = (2+2) = 4, A₄ = 8, Now if we soar extra subsequent Okay_th 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, Okay = 4, X[] = {1, 4, 5, 50}
Output: 50
Rationalization: Will probably be optimum to decide on i = 4 then A₄ = 50. So the subsequence turns into {50}. Now, subsequent (i+Okay_th) index doesn’t exist. Subsequently 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.

Method: Implement the thought beneath to resolve the issue

The issue is Grasping logic primarily based and might be solved utilizing the observations. 

Steps have been taken to resolve 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 comply with the below-mentioned steps below the scope of the loop:
  • Y[i] = i + Okay < 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:

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