Dada una array de tamaño n. Encuentra la suma máxima de una subsecuencia creciente.
Ejemplos:
Input : arr[] = { 1, 20, 4, 2, 5 }
Output : Maximum sum of increasing subsequence is = 21
The subsequence 1, 20 gives maximum sum which is 21
Input : arr[] = { 4, 2, 3, 1, 5, 8 }
Output : Maximum sum of increasing subsequence is = 18
The subsequence 2, 3, 5, 8 gives maximum sum which is 18
Requisito previo
La solución utiliza el mapa y el árbol indexado binario .
Enfoque de programación dinámica: enfoque DP que está en O (n ^ 2) .
Solución
Paso 1:
el primer paso es insertar todos los valores en un mapa, luego podemos asignar estos valores de array a los índices del árbol indexado binario.
Paso 2:
iterar el mapa y asignar índices. Lo que esto haría es para una array { 4, 2, 3, 8, 5, 2 }
2 se le asignará el índice 1
3 se le asignará el índice 2
4 se le asignará el índice 3
5 se le asignará el índice 4
8 se le asignará el índice 5
Paso 3:
Construya el árbol indexado binario.
Paso 4 :
Para cada valor en la array dada, haga lo siguiente.
Encuentre la suma máxima hasta esa posición usando BIT y luego actualice el BIT con el Nuevo valor máximo
Paso 5:
Devuelve la suma máxima que está presente en la última posición en el árbol indexado binario.
C++
// C++ code for Maximum Sum
// Increasing Subsequence
#include <bits/stdc++.h>
using namespace std;
// Returns the maximum value of
// the increasing subsequence
// till that index
// Link to understand getSum function
// https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
int getSum(int BITree[], int index)
{
int sum = 0;
while (index > 0) {
sum = max(sum, BITree[index]);
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index
// Tree (BITree) at given index in
// BITree. The max value is updated
// by taking max of 'val' and the
// already present value in the node.
void updateBIT(int BITree[], int newIndex,
int index, int val)
{
while (index <= newIndex) {
BITree[index] = max(val, BITree[index]);
index += index & (-index);
}
}
// maxSumIS() returns the maximum
// sum of increasing subsequence
// in arr[] of size n
int maxSumIS(int arr[], int n)
{
int newindex = 0, max_sum;
map<int, int> uniqueArr;
// Inserting all values in map uniqueArr
for (int i = 0; i < n; i++) {
uniqueArr[arr[i]] = 0;
}
// Assigning indexes to all
// the values present in map
for (map<int, int>::iterator it = uniqueArr.begin();
it != uniqueArr.end(); it++) {
// newIndex is actually the count of
// unique values in the array.
newindex++;
uniqueArr[it->first] = newindex;
}
// Constructing the BIT
int* BITree = new int[newindex + 1];
// Initializing the BIT
for (int i = 0; i <= newindex; i++) {
BITree[i] = 0;
}
for (int i = 0; i < n; i++) {
// Finding maximum sum till this element
max_sum = getSum(BITree, uniqueArr[arr[i]] - 1);
// Updating the BIT with new maximum sum
updateBIT(BITree, newindex,
uniqueArr[arr[i]], max_sum + arr[i]);
}
// return maximum sum
return getSum(BITree, newindex);
}
// Driver program
int main()
{
int arr[] = { 1, 101, 2, 3, 100, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum is = " << maxSumIS(arr, n);
return 0;
}
Java
// JAVA code for Maximum Sum
// Increasing Subsequence
import java.util.*;
class GFG{
// Returns the maximum value of
// the increasing subsequence
// till that index
// Link to understand getSum function
// https://www.geeksforgeeks.org/
// binary-indexed-tree-or-fenwick-tree-2/
static int getSum(int BITree[], int index)
{
int sum = 0;
while (index > 0)
{
sum = Math.max(sum,
BITree[index]);
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index
// Tree (BITree) at given index in
// BITree. The max value is updated
// by taking max of 'val' and the
// already present value in the node.
static void updateBIT(int BITree[],
int newIndex,
int index, int val)
{
while (index <= newIndex)
{
BITree[index] = Math.max(val,
BITree[index]);
index += index & (-index);
}
}
// maxSumIS() returns the maximum
// sum of increasing subsequence
// in arr[] of size n
static int maxSumIS(int arr[],
int n)
{
int newindex = 0, max_sum;
HashMap<Integer,
Integer> uniqueArr =
new HashMap<>();
// Inserting all values in map
// uniqueArr
for (int i = 0; i < n; i++)
{
uniqueArr.put(arr[i], 0);
}
// Assigning indexes to all
// the values present in map
for (Map.Entry<Integer,
Integer> entry :
uniqueArr.entrySet())
{
// newIndex is actually the
// count of unique values in
// the array.
newindex++;
uniqueArr.put(entry.getKey(),
newindex);
}
// Constructing the BIT
int []BITree = new int[newindex + 1];
// Initializing the BIT
for (int i = 0; i <= newindex; i++)
{
BITree[i] = 0;
}
for (int i = 0; i < n; i++)
{
// Finding maximum sum till
// this element
max_sum = getSum(BITree,
uniqueArr.get(arr[i]) - 3);
// Updating the BIT with
// new maximum sum
updateBIT(BITree, newindex,
uniqueArr.get(arr[i]),
max_sum + arr[i]);
}
// return maximum sum
return getSum(BITree,
newindex);
}
// Driver program
public static void main(String[] args)
{
int arr[] = {1, 101, 2,
3, 100, 4, 5};
int n = arr.length;
System.out.print("Maximum sum is = " +
maxSumIS(arr, n));
}
}
// This code is contributed by shikhasingrajput
C#
// C# code for Maximum Sum
// Increasing Subsequence
using System;
using System.Collections.Generic;
class GFG{
// Returns the maximum value of
// the increasing subsequence
// till that index
// Link to understand getSum function
// https://www.geeksforgeeks.org/
// binary-indexed-tree-or-fenwick-tree-2/
static int getSum(int []BITree,
int index)
{
int sum = 0;
while (index > 0)
{
sum = Math.Max(sum,
BITree[index]);
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index
// Tree (BITree) at given index in
// BITree. The max value is updated
// by taking max of 'val' and the
// already present value in the node.
static void updateBIT(int []BITree,
int newIndex,
int index, int val)
{
while (index <= newIndex)
{
BITree[index] = Math.Max(val,
BITree[index]);
index += index & (-index);
}
}
// maxSumIS() returns the maximum
// sum of increasing subsequence
// in []arr of size n
static int maxSumIS(int []arr,
int n)
{
int newindex = 0, max_sum;
Dictionary<int,
int> uniqueArr =
new Dictionary<int,
int>();
// Inserting all values in map
// uniqueArr
for (int i = 0; i < n; i++)
{
uniqueArr.Add(arr[i], 0);
}
Dictionary<int,
int> uniqueArr1 =
new Dictionary<int,
int>();
// Assigning indexes to all
// the values present in map
foreach (KeyValuePair<int,
int> entry in
uniqueArr)
{
// newIndex is actually the
// count of unique values in
// the array.
newindex++;
if(uniqueArr1.ContainsKey(entry.Key))
uniqueArr1[entry.Key] = newindex;
else
uniqueArr1.Add(entry.Key,
newindex);
}
// Constructing the BIT
int []BITree = new int[newindex + 1];
// Initializing the BIT
for (int i = 0; i <= newindex; i++)
{
BITree[i] = 0;
}
for (int i = 0; i < n; i++)
{
// Finding maximum sum till
// this element
max_sum = getSum(BITree,
uniqueArr1[arr[i]] - 4);
// Updating the BIT with
// new maximum sum
updateBIT(BITree, newindex,
uniqueArr1[arr[i]],
max_sum + arr[i]);
}
// return maximum sum
return getSum(BITree,
newindex);
}
// Driver program
public static void Main(String[] args)
{
int []arr = {1, 101, 2,
3, 100, 4, 5};
int n = arr.Length;
Console.Write("Maximum sum is = " +
maxSumIS(arr, n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for Maximum Sum
// Increasing Subsequence
// Returns the maximum value of
// the increasing subsequence
// till that index
// Link to understand getSum function
// https://www.geeksforgeeks.org/
// binary-indexed-tree-or-fenwick-tree-2/
function getSum(BITree, index)
{
var sum = 0;
while (index > 0)
{
sum = Math.max(sum,
BITree[index]);
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index
// Tree (BITree) at given index in
// BITree. The max value is updated
// by taking max of 'val' and the
// already present value in the node.
function updateBIT(BITree, newIndex, index, val)
{
while (index <= newIndex)
{
BITree[index] = Math.max(val,
BITree[index]);
index += index & (-index);
}
}
// maxSumIS() returns the maximum
// sum of increasing subsequence
// in []arr of size n
function maxSumIS(arr, n)
{
var newindex = 0, max_sum;
var uniqueArr = new Map();
// Inserting all values in map
// uniqueArr
for (var i = 0; i < n; i++)
{
uniqueArr.set(arr[i], 0);
}
var uniqueArr1 = new Map();
// Assigning indexes to all
// the values present in map
uniqueArr.forEach((value, key) => {
// newIndex is actually the
// count of unique values in
// the array.
newindex++;
uniqueArr1.set(key, newindex);
});
// Constructing the BIT
var BITree = Array(newindex+1).fill(0);
for (var i = 0; i < n; i++)
{
// Finding maximum sum till
// this element
max_sum = getSum(BITree,
uniqueArr1.get(arr[i]) - 4);
// Updating the BIT with
// new maximum sum
updateBIT(BITree, newindex,
uniqueArr1.get(arr[i]),
max_sum + arr[i]);
}
// return maximum sum
return getSum(BITree,
newindex);
}
// Driver program
var arr = [1, 101, 2,
3, 100, 4, 5];
var n = arr.length;
document.write("Maximum sum is = " +
maxSumIS(arr, n));
</script>
Python3
# python code for Maximum Sum
# Increasing Subsequence
# Returns the maximum value of
# the increasing subsequence
# till that index
# Link to understand getSum function
def getSum(BITree, index):
sum = 0
while (index > 0):
sum = max(sum, BITree[index])
index -= index & (-index)
return sum
# Updates a node in Binary Index
# Tree (BITree) at given index in
# BITree. The max value is updated
# by taking max of 'val' and the
# already present value in the node.
def updateBIT(BITree, newIndex, index, val):
while (index <= newIndex):
BITree[index] = max(val, BITree[index])
index += index & (-index)
# maxSumIS() returns the maximum
# sum of increasing subsequence
# in arr[] of size n
def maxSumIS(arr, n):
newindex = 0
max_sum = 0
uniqueArr = {}
# Inserting all values in map uniqueArr
for i in range(0, n):
uniqueArr[arr[i]] = 0
# Assigning indexes to all
# the values present in map
for it in sorted(uniqueArr):
# newIndex is actually the count of
# unique values in the array.
newindex += 1
uniqueArr[it] = newindex
# Constructing the BIT
BITree = [0]*(newindex + 1)
# Initializing the BIT
for i in range(0, newindex+1):
BITree[i] = 0
for i in range(0, n):
# Finding maximum sum till this element
max_sum = getSum(BITree, uniqueArr[arr[i]] - 1)
# Updating the BIT with new maximum sum
updateBIT(BITree, newindex, uniqueArr[arr[i]], max_sum + arr[i])
# return maximum sum
return getSum(BITree, newindex)
# Driver program
arr = [1, 101, 2, 3, 100, 4, 5]
n = len(arr)
print("Maximum sum is = ", maxSumIS(arr, n))
# This code is contributed by rj13to.
Producción
Maximum sum is = 106
Tenga
en cuenta la complejidad temporal de la solución
O(nLogn) para el mapa y O(nLogn) para actualizar y obtener la suma. Entonces, la complejidad general sigue siendo O (nLogn).
Publicación traducida automáticamente
Artículo escrito por Jeevan Jadon y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA