Dada una secuencia de array arr[], es decir , [A 1 , A 2 …A n ] y un entero k , la tarea es encontrar la suma máxima posible de la subsecuencia creciente S de longitud k tal que S 1 <=S 2 <=S 3 ………<=S k .
Ejemplos:
Entrada: arr[] = {-1, 3, 4, 2, 5}, K = 3
Salida: 3 4 5
Explicación: La subsecuencia 3 4 5 con suma 12 es la subsecuencia con suma máxima posible.
Entrada: arr[] = {6, 3, 4, 1, 1, 8, 7, -4, 2}
Salida: 6 3 4 8 7
Enfoque: la tarea se puede resolver usando Enfoque codicioso . La idea es tomar el máximo de elementos posibles de arr[] en la subsecuencia. Siga los pasos a continuación para resolver el problema.
- Declare un vector de contenedor de pares, por ejemplo, use [] para almacenar elementos con sus índices.
- Atraviesa arr[] y empuja todos los elementos en uso[] con sus índices.
- Ordenar uso[] en orden no decreciente .
- Declare un vector ans[] para almacenar la subsecuencia final.
- Atraviese use[] con i y tome el último elemento K del uso y empuje sus índices ( use[i].second ) en ans[] .
- Ordene ans[] en orden no decreciente para que los índices estén en orden creciente.
- Ahora atraviesa ans[] con i y reemplaza cada elemento con arr[ans[i]] .
- Devuelve ans[] como la subsecuencia de suma máxima final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the subsequence
// with maximum sum of length K
vector<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 Code
int 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 approach
import 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 K def 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 Code if __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 approach
using 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>
Producción
6 3 4 8 7
Complejidad de tiempo : O(NlogN), donde N es el tamaño de la array
Espacio auxiliar : O(N), donde N es el tamaño de la array
Publicación traducida automáticamente
Artículo escrito por coder_nero y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA