Dada una array A[] de tamaño N , la tarea es encontrar la suma máxima de una subsecuencia tal que para cada par presente en la subsecuencia , la diferencia entre sus índices en la array original sea igual a la diferencia entre sus valores.
Ejemplos:
Entrada: A[] = {10, 7, 1, 9, 10, 15}, N = 6
Salida: 26
Explicación:
Subsecuencia: {7, 9, 10}.
Los índices en la array original son {1, 3, 4} respectivamente.
La diferencia entre sus índices y valores es igual para todos los pares.
Por lo tanto, la suma máxima posible = (7 + 9 + 10) = 26.Entrada: A[] = {100, 2}, N = 2
Salida: 100
Enfoque: para dos elementos que tienen índices i y j , y valores A[i] y A[j], si i – j es igual a A[i] – A[j], entonces A[i] – i es igual a A[j] – j . Por lo tanto, la subsecuencia válida tendrá el mismo valor de A[i] – i . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0, para almacenar la suma máxima posible de una subsecuencia requerida .
- Inicialice un mapa , digamos mp, para almacenar el valor de cada A[i] – i .
- Iterar en el rango [0, N – 1] usando una variable, digamos i :
- Agregue A[i] a mp[A[i] – i].
- Actualice ans como el máximo de ans y mp[A[i] – i].
- Finalmente, imprima ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// a subsequence having difference between
// indices equal to difference in their values
void maximumSubsequenceSum(int A[], int N)
{
// Stores the maximum sum
int ans = 0;
// Stores the value for each A[i] - i
map<int, int> mp;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update the value in map
mp[A[i] - i] += A[i];
// Update the answer
ans = max(ans, mp[A[i] - i]);
}
// Finally, print the answer
cout << ans << endl;
}
// Driver Code
int main()
{
// Given Input
int A[] = { 10, 7, 1, 9, 10, 1 };
int N = sizeof(A) / sizeof(A[0]);
// Function Call
maximumSubsequenceSum(A, N);
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
public class GFG
{
// Function to find the maximum sum of
// a subsequence having difference between
// indices equal to difference in their values
static void maximumSubsequenceSum(int A[], int N)
{
// Stores the maximum sum
int ans = 0;
// Stores the value for each A[i] - i
HashMap<Integer, Integer> mp = new HashMap<>();
// Traverse the array
for (int i = 0; i < N; i++) {
// Update the value in map
mp.put(A[i] - i,
mp.getOrDefault(A[i] - i, 0) + A[i]);
// Update the answer
ans = Math.max(ans, mp.get(A[i] - i));
}
// Finally, print the answer
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
// Given Input
int A[] = { 10, 7, 1, 9, 10, 1 };
int N = A.length;
// Function Call
maximumSubsequenceSum(A, N);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach
# Function to find the maximum sum of
# a subsequence having difference between
# indices equal to difference in their values
def maximumSubsequenceSum(A, N):
# Stores the maximum sum
ans = 0
# Stores the value for each A[i] - i
mp = {}
# Traverse the array
for i in range(N):
if (A[i] - i in mp):
# Update the value in map
mp[A[i] - i] += A[i]
else:
mp[A[i] - i] = A[i]
# Update the answer
ans = max(ans, mp[A[i] - i])
# Finally, print the answer
print(ans)
# Driver Code
if __name__ == '__main__':
# Given Input
A = [ 10, 7, 1, 9, 10, 1 ]
N = len(A)
# Function Call
maximumSubsequenceSum(A, N)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System.Collections.Generic;
using System;
class GFG{
// Function to find the maximum sum of
// a subsequence having difference between
// indices equal to difference in their values
static void maximumSubsequenceSum(int []A, int N)
{
// Stores the maximum sum
int ans = 0;
// Stores the value for each A[i] - i
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update the value in map
if (mp.ContainsKey(A[i] - i))
mp[A[i] - i] += A[i];
else
mp[A[i] - i] = A[i];
// Update the answer
ans = Math.Max(ans, mp[A[i] - i]);
}
// Finally, print the answer
Console.Write(ans);
}
// Driver code
public static void Main(String[] args)
{
// Given Input
int []A = { 10, 7, 1, 9, 10, 1 };
int N = A.Length;
// Function Call
maximumSubsequenceSum(A, N);
}
}
// This code is contributed by amreshkumar3
Javascript
<script>
// javascript program for the above approach
// Function to find the maximum sum of
// a subsequence having difference between
// indices equal to difference in their values
function maximumSubsequenceSum(A, N)
{
// Stores the maximum sum
var ans = 0;
// Stores the value for each A[i] - i
var mp = new Map();
var i;
// Traverse the array
for(i = 0; i < N; i++) {
// Update the value in map
if(mp.has(A[i] - i))
mp.set(A[i] - i,mp.get(A[i] - i)+A[i]);
else
mp.set(A[i] - i,A[i]);
// Update the answer
ans = Math.max(ans, mp.get(A[i] - i));
}
// Finally, print the answer
document.write(ans);
}
// Driver Code
// Given Input
var A = [10, 7, 1, 9, 10, 1];
var N = A.length;
// Function Call
maximumSubsequenceSum(A, N);
</script>
26
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA