Given an array X[] of length N along with an integer K. Then the task is to choose a sub-sequence to maximize the sum by selecting the starting index i
(1 ? i ? N ) and make the subsequence of all the elements, which are at a continuous distance (i + K) till we are not out of the array X[] or at the last index.
Examples:
Input: N = 5, K = 2, X[] = {2, 5, 5, 8, 2}
Output: 13
Explanation: The operation is performed as:
- Let select index i = 2 and then A2 = 5 So that next element at Kth distance from i = (i + K) = (2+2) = 4, A4 = 8, Now if we jump more next Kth index, formally (4 + 2) = 6. So it doesn’t exist or we are out of the X[]. So the subsequence becomes = {5, 8}, Which gives sum as 13. Which is maximum possible.
Input: N = 4, K = 4, X[] = {1, 4, 5, 50}
Output: 50
Explanation: It will be optimal to choose i = 4 then A4 = 50. So the subsequence becomes {50}. Now, next (i+Kth) index doesn’t exist. Therefore the subsequence has sum as 50. Which is maximum possible. It can be verified that no sum more than 50 is possible using the given operation.
Approach: Implement the idea below to solve the problem
The problem is Greedy logic based and can be solved using the observations.
Steps were taken to solve the problem:
- Create an array of length N let’s say Y[].
- Create a variable let’s say max and initialize it to a minimum integer value for storing the maximum possible sum.
- Run a loop from i = N-1 to i ? 0 and follow the below-mentioned steps under the scope of the loop:
- Y[i] = i + K < N ? X[i] + Y[i + K] : X[i]
- Now just find the maximum value from Y[] by traversing it and updating the max
- Output the value of max.
Below is the code to implement the approach:
C++
// C++ code to implement the approach#include <iostream>#include <bits/stdc++.h>using namespace std;// Method for getting maximum// subsequence sumvoid MaxSubsequenceSum(int N, int K, int X[]){ int l = INT_MIN; // New array formed of size N int Y[N]; // Variable for holding // maximum sum int sum = INT_MIN; // Traversing through loop and // applying logic for (int i = N - 1; i >= 0; i--) { Y[i] = i + K < N ? X[i] + Y[i + K] : X[i]; } // Finding max from the array Y[] for (int i = 0; i < N; i++) { sum = max(Y[i], sum); } // Printing maximum possible sum cout<<sum<<endl; }int main() { // Inputs int N = 5; int K = 2; int X[] = { 2, 5, 5, 8, 2 }; // Function call MaxSubsequenceSum(N, K, X); return 0;}// This code is contributed by Ritesh Jha |
Java
// Java code to implement the approachpublic class Main { // Driver function public static void main(String[] args) { // Inputs int N = 5; int K = 2; int X[] = { 2, 5, 5, 8, 2 }; // Function call MaxSubsequenceSum(N, K, X); } // Method for getting maximum // subsequence sum static void MaxSubsequenceSum(int N, int K, int[] X) { int l = Integer.MIN_VALUE; // New array formed of size N int Y[] = new int[N]; // Variable for holding // maximum sum int max = Integer.MIN_VALUE; // Traversing through loop and // applying logic for (int i = N - 1; i >= 0; i--) { Y[i] = i + K < N ? X[i] + Y[i + K] : X[i]; } // Finding max from the array Y[] for (int i = 0; i < N; i++) { max = Math.max(Y[i], max); } // Printing maximum possible sum System.out.println(max); }} |
Python3
import sys# Method for getting maximum# subsequence sumdef MaxSubsequenceSum(N, K, X): l = -sys.maxsize - 1 # New array formed of size N Y = [0] * N # Variable for holding # maximum sum sum = -sys.maxsize - 1 # Traversing through loop and # applying logic for i in range(N - 1, -1, -1): Y[i] = X[i] + Y[i + K] if i + K < N else X[i] # Finding max from the array Y[] for i in range(N): sum = max(Y[i], sum) # Printing maximum possible sum print(sum)# InputsN = 5K = 2X = [2, 5, 5, 8, 2]# Function callMaxSubsequenceSum(N, K, X) |
C#
// C# code to implement the approachusing System;public class GFG { // Method for getting maximum subsequence sum static void MaxSubsequenceSum(int N, int K, int[] X) { int l = Int32.MinValue; // New array formed of size N int[] Y = new int[N]; // Variable for holding maximum sum int max = Int32.MinValue; // Traversing through loop and applying logic for (int i = N - 1; i >= 0; i--) { Y[i] = i + K < N ? X[i] + Y[i + K] : X[i]; } // Finding max from the array Y[] for (int i = 0; i < N; i++) { max = Math.Max(Y[i], max); } // Printing maximum possible sum Console.WriteLine(max); } static public void Main() { // Code // Inputs int N = 5; int K = 2; int[] X = { 2, 5, 5, 8, 2 }; // Function call MaxSubsequenceSum(N, K, X); }}// This code is contributed by sankar. |
Javascript
// JavaScript code to implement the approach// Method for getting maximum// subsequence sumfunction MaxSubsequenceSum(N, K, X){ let l = Number.MIN_SAFE_INTEGER; // New array formed of size N let Y = new Array(N); // Variable for holding // maximum sum let sum = Number.MIN_SAFE_INTEGER; // Traversing through loop and // applying logic for (let i = N - 1; i >= 0; i--) { Y[i] = i + K < N ? X[i] + Y[i + K] : X[i]; } // Finding max from the array Y[] for (let i = 0; i < N; i++) { sum = Math.max(Y[i], sum); } // Printing maximum possible sum console.log(sum);}// Inputslet N = 5;let K = 2;let X = [ 2, 5, 5, 8, 2 ];// Function callMaxSubsequenceSum(N, K, X);// This code is contributed by prasad264 |
Output
13
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments