Given an array sequence arr[] i.e [A1, A2 …An] and an integer k, the task is to find the maximum possible sum of increasing subsequence S of length k such that S1<=S2<=S3………<=Sk.
Examples:
Input: arr[] = {-1, 3, 4, 2, 5}, K = 3
Output: 3 4 5
Explanation: Subsequence 3 4 5 with sum 12 is the subsequence with maximum possible sum.
Input: arr[] = {6, 3, 4, 1, 1, 8, 7, -4, 2}
Output: 6 3 4 8 7
Approach: The task can be solved using Greedy Approach. The idea is to take the maximum possible elements from arr[] in the subsequence. Follow the steps below to solve the problem.
- Declare a vector of pairs container say, use[] to store elements with their indices.
- Traverse arr[] and push all the elements in use[] with their indices.
- Sort use[] in non-decreasing order.
- Declare a vector ans[] to store the final subsequence.
- Traverse use[] with i and Take the last K element from use and push their indices(use[i].second) into ans[].
- Sort ans[] in non-decreasing order so that indices should be in increasing order.
- Now Traverse ans[] with i and replace each element with arr[ans[i]].
- Return ans[] as the final maximum sum subsequence.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find the subsequence// with maximum sum of length Kvector<int> maxSumSubsequence(vector<int>& arr, int N, int K){ // Use an extra array to keep // track of indices while sorting vector<pair<int, int> > use; for (int i = 0; i < N; i++) { use.push_back({ arr[i], i }); } // Sorting in non-decreasing order sort(use.begin(), use.end()); // To store the final subsequence vector<int> ans; // Pushing last K elements in ans for (int i = N - 1; i >= N - K; i--) { // Pushing indices of elements // which are part of final subsequence ans.push_back(use[i].second); } // Sorting the indices sort(ans.begin(), ans.end()); // Storing elements corresponding to each indices for (int i = 0; i < int(ans.size()); i++) ans[i] = arr[ans[i]]; // Return ans as the final result return ans;}// Driver Codeint main(){ int N = 9; vector<int> arr = { 6, 3, 4, 1, 1, 8, 7, -4, 2 }; int K = 5; // Storing answer in res vector<int> res = maxSumSubsequence(arr, N, K); // Printing the result for (auto i : res) cout << i << ' '; return 0;} |
Java
// Java program for above approachimport java.util.ArrayList;import java.util.Collections;import java.util.Comparator;class GFG { static class Pair { int first; int second; Pair(int i, int j) { this.first = i; this.second = j; } } // Function to find the subsequence // with maximum sum of length K static ArrayList<Integer> maxSumSubsequence(int[] arr, int N, int K) { // Use an extra array to keep // track of indices while sorting ArrayList<Pair> use = new ArrayList<Pair>(); for (int i = 0; i < N; i++) { use.add(new Pair(arr[i], i)); } // Sorting in non-decreasing order Collections.sort(use, new Comparator<Pair>() { @Override public int compare(Pair i, Pair j) { return i.first - j.first; } }); // To store the final subsequence ArrayList<Integer> ans = new ArrayList<Integer>(); // Pushing last K elements in ans for (int i = N - 1; i >= N - K; i--) { // Pushing indices of elements // which are part of final subsequence ans.add(use.get(i).second); } // Sorting the indices Collections.sort(ans); // Storing elements corresponding to each indices for (int i = 0; i < ans.size(); i++) ans.set(i, arr[ans.get(i)]); // Return ans as the final result return ans; } // Driver Code public static void main(String args[]) { int N = 9; int[] arr = { 6, 3, 4, 1, 1, 8, 7, -4, 2 }; int K = 5; // Storing answer in res ArrayList<Integer> res = maxSumSubsequence(arr, N, K); // Printing the result for (int i : res) System.out.print(i + " "); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python program for above approach# Function to find the subsequence# with maximum sum of length Kdef maxSumSubsequence(arr, N, K): # Use an extra array to keep # track of indices while sorting use = [] for i in range(0, N): use.append([arr[i], i]) # Sorting in non-decreasing order use.sort() # To store the final subsequence ans = [] # Pushing last K elements in ans for i in range(N - 1, N - K - 1, -1): # Pushing indices of elements # which are part of final subsequence ans.append(use[i][1]) # Sorting the indices ans.sort() # Storing elements corresponding to each indices for i in range(0, len(ans)): ans[i] = arr[ans[i]] # Return ans as the final result return ans# Driver Codeif __name__ == "__main__": N = 9 arr = [6, 3, 4, 1, 1, 8, 7, -4, 2] K = 5 # Storing answer in res res = maxSumSubsequence(arr, N, K) # Printing the result for i in res: print(i, end=' ') # This code is contributed by rakeshsahni |
C#
// C# program for above approachusing System;using System.Collections.Generic;public class GFG { class Pair { public int first; public int second; public Pair(int i, int j) { this.first = i; this.second = j; } } // Function to find the subsequence // with maximum sum of length K static List<int> maxSumSubsequence(int[] arr, int N, int K) { // Use an extra array to keep // track of indices while sorting List<Pair> use = new List<Pair>(); for (int i = 0; i < N; i++) { use.Add(new Pair(arr[i], i)); } // Sorting in non-decreasing order use.Sort((i, j) => i.first - j.first); // To store the readonly subsequence List<int> ans = new List<int>(); // Pushing last K elements in ans for (int i = N - 1; i >= N - K; i--) { // Pushing indices of elements // which are part of readonly subsequence ans.Add(use[i].second); } // Sorting the indices ans.Sort(); // Storing elements corresponding to each indices for (int i = 0; i < ans.Count; i++) ans[i] = arr[ans[i]]; // Return ans as the readonly result return ans; } // Driver Code public static void Main(String []args) { int N = 9; int[] arr = { 6, 3, 4, 1, 1, 8, 7, -4, 2 }; int K = 5; // Storing answer in res List<int> res = maxSumSubsequence(arr, N, K); // Printing the result foreach (int i in res) Console.Write(i + " "); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Function to find the subsequence // with maximum sum of length K function maxSumSubsequence(arr, N, K) { // Use an extra array to keep // track of indices while sorting let use = []; for (let i = 0; i < N; i++) { use.push({ first: arr[i], second: i }); } // Sorting in non-decreasing order use.sort(function (a, b) { return a.first - b.first; }); // To store the final subsequence let ans = []; // Pushing last K elements in ans for (let i = N - 1; i >= N - K; i--) { // Pushing indices of elements // which are part of final subsequence ans.push(use[i].second); } // Sorting the indices ans.sort(function (a, b) { return a - b; }); // Storing elements corresponding to each indices for (let i = 0; i < ans.length; i++) ans[i] = arr[ans[i]]; // Return ans as the final result return ans; } // Driver Code let N = 9; let arr = [6, 3, 4, 1, 1, 8, 7, -4, 2] let K = 5; // Storing answer in res let res = maxSumSubsequence(arr, N, K); // Printing the result for (let i = 0; i < res.length; i++) document.write(res[i] + ' ');// This code is contributed by Potta Lokesh </script> |
Output
6 3 4 8 7
Time Complexity: O(NlogN), where N is the size of the array
Auxiliary Space: O(N), Where N is the size of the array
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!
