Maximiza la suma de números en un máximo de K movimientos en el rango [L, R]

Dada una array arr[] de N enteros y Q consultas. Cada consulta consta de 3 números enteros L , R y K . Puede pasar del índice i al índice i + 1 en un solo paso o permanecer en ese índice en particular en un solo paso. Puede pasar del índice L al R en un máximo de K pasos e imprimir la suma de cada número en el que estaba en cada paso, incluido el L-ésimo número. La tarea es maximizar la suma en un máximo de K movimientos. Si no podemos movernos de L a R enK pasos y luego escriba “No”
Ejemplos: 
 

Entrada: arr[] = {1, 3, 2, -4, -5}, q = { 
{0, 2, 2}, 
{0, 2, 4}, 
{3, 4, 1}, 
{0, 4, 2}} 
Salida: 

12 
-9 
No
Para la primera consulta: 
En el primer paso, muévase del índice 0 al índice 1, por lo tanto, 1 + 3 = 4 
En el segundo paso, muévase del índice 1 al índice 2, por lo tanto, 4 + 2 = 6
Para la segunda consulta: 
En el primer paso, muévase del índice 0 al índice 1, por lo tanto, 1 + 3 = 4 
En el segundo paso, quédese en el índice 1, por lo tanto, 4 + 3 = 7 
En el tercer paso, quédese nuevamente en el índice 1, por lo tanto, 7 + 3 = 10 
En el cuarto paso, pase del primer índice al segundo índice solamente, por lo tanto, 10 + 2 = 12 
 

Un enfoque ingenuo es verificar primero si L – R > K , si es así, no podemos movernos del índice L al R en K pasos. Iterar de L a R , obtener la suma de todos los elementos entre L y R . Luego encuentre el elemento máximo en el rango L y R y la respuesta será la suma de los elementos en el rango y (K – (R – L)) * máximo . Si el máximo es un número negativo, realizamos exactamente los movimientos R – L; de lo contrario, realizamos los pasos adicionales en el índice de número máximo en el rango [L, R]
Complejidad de tiempo: O(R – L) por consulta. 
Un enfoque eficiente es usar el árbol de segmentos en el rango [L, R] para encontrar el número máximo y encontrar la suma en el rango usando el prefijo sum .
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to create the tree
void tree(int low, int high, int pos,
          int b[], int a[], int n)
{
    // Leaf nodes
    if (low == high) {
        b[pos] = a[high];
        return;
    }
    int mid = (high + low) / 2;
 
    // Left subtree
    tree(low, mid, 2 * pos + 1, b, a, n);
 
    // Right subtree
    tree(mid + 1, high, 2 * pos + 2, b, a, n);
 
    // Merge the maximum
    b[pos] = max(b[2 * pos + 1], b[2 * pos + 2]);
}
 
// Function that returns the maximum in range L and R
int rangemax(int s, int e, int low, int high,
             int pos, int b[], int a[], int n)
{
    // Complete overlap
    if (low <= s && high >= e)
        return b[pos];
 
    // Out of range completely
    if (e < low || s > high)
        return INT_MIN;
    int mid = (s + e) / 2;
 
    // Find maximum in left and right subtrees
    int left = rangemax(s, mid, low, high,
                        2 * pos + 1, b, a, n);
    int right = rangemax(mid + 1, e, low, high,
                         2 * pos + 2, b, a, n);
 
    // Return the maximum of both
    return max(left, right);
}
 
// Function that solves a query
int solveQuery(int l, int r, int k, int n, int a[],
               int b[], int prefix[])
{
 
    // If there are ko
    if (r - l > k)
        return -1;
 
    // Find maximum in range L and R
    int maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
 
    // If maximum is 0
    if (maximum < 0)
        maximum = 0;
 
    // Find the prefix sum
    int rangesum = prefix[r];
 
    // If not first element
    if (l > 0)
        rangesum -= prefix[l - 1];
 
    // Get the answer
    int answer = rangesum + (k - (r - l)) * maximum;
 
    return answer;
}
 
// Function that solves the queries
void solveQueries(int n, int a[], int b[],
                  int prefix[], int queries[][3], int q)
{
 
    // Solve all the queries
    for (int i = 0; i < q; i++) {
        int ans = solveQuery(queries[i][0], queries[i][1],
                             queries[i][2], n, a, b, prefix);
        if (ans != -1)
            cout << ans << endl;
        else
            cout << "No" << endl;
    }
}
 
// Function to find the prefix sum
void findPrefixSum(int prefix[], int a[], int n)
{
    prefix[0] = a[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
}
 
// Driver code
int main()
{
    int a[] = { 1, 3, 2, -4, -5 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // Array for segment tree
    int b[5 * n];
 
    // Create segment tree
    tree(0, n - 1, 0, b, a, n);
 
    int prefix[n];
 
    // Fill prefix sum array
    findPrefixSum(prefix, a, n);
 
    // Queries
    int queries[][3] = { { 0, 2, 2 },
                         { 0, 2, 4 },
                         { 3, 4, 1 },
                         { 0, 4, 2 } };
 
    int q = sizeof(queries) / sizeof(queries[0]);
    solveQueries(n, a, b, prefix, queries, q);
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
 
// Function to create the tree
static void tree(int low, int high, int pos,
        int b[], int a[], int n)
{
    // Leaf nodes
    if (low == high)
    {
        b[pos] = a[high];
        return;
    }
    int mid = (high + low) / 2;
 
    // Left subtree
    tree(low, mid, 2 * pos + 1, b, a, n);
 
    // Right subtree
    tree(mid + 1, high, 2 * pos + 2, b, a, n);
 
    // Merge the maximum
    b[pos] = Math.max(b[2 * pos + 1], b[2 * pos + 2]);
}
 
// Function that returns the maximum in range L and R
static int rangemax(int s, int e, int low, int high,
            int pos, int b[], int a[], int n)
{
    // Complete overlap
    if (low <= s && high >= e)
        return b[pos];
 
    // Out of range completely
    if (e < low || s > high)
        return Integer.MIN_VALUE;
    int mid = (s + e) / 2;
 
    // Find maximum in left and right subtrees
    int left = rangemax(s, mid, low, high,
                        2 * pos + 1, b, a, n);
    int right = rangemax(mid + 1, e, low, high,
                        2 * pos + 2, b, a, n);
 
    // Return the maximum of both
    return Math.max(left, right);
}
 
// Function that solves a query
static int solveQuery(int l, int r, int k, int n, int a[],
                                    int b[], int prefix[])
{
 
    // If there are ko
    if (r - l > k)
        return -1;
 
    // Find maximum in range L and R
    int maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
 
    // If maximum is 0
    if (maximum < 0)
        maximum = 0;
 
    // Find the prefix sum
    int rangesum = prefix[r];
 
    // If not first element
    if (l > 0)
        rangesum -= prefix[l - 1];
 
    // Get the answer
    int answer = rangesum + (k - (r - l)) * maximum;
 
    return answer;
}
 
// Function that solves the queries
static void solveQueries(int n, int a[], int b[],
                int prefix[], int queries[][], int q)
{
 
    // Solve all the queries
    for (int i = 0; i < q; i++)
    {
        int ans = solveQuery(queries[i][0], queries[i][1],
                            queries[i][2], n, a, b, prefix);
        if (ans != -1)
            System.out.println(ans);
        else
            System.out.println("No" );
    }
}
 
// Function to find the prefix sum
static void findPrefixSum(int prefix[], int a[], int n)
{
    prefix[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 3, 2, -4, -5 };
    int n = a.length;
 
    // Array for segment tree
    int b[] = new int[5 * n];
 
    // Create segment tree
    tree(0, n - 1, 0, b, a, n);
 
    int prefix[] = new int[n];
 
    // Fill prefix sum array
    findPrefixSum(prefix, a, n);
 
    // Queries
    int queries[][] = { { 0, 2, 2 },
                        { 0, 2, 4 },
                        { 3, 4, 1 },
                        { 0, 4, 2 } };
 
    int q = queries.length;
    solveQueries(n, a, b, prefix, queries, q);
 
}
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 implementation of the approach
 
# Function to create the tree
def tree( low, high, pos, b, a, n):
     
    # Leaf nodes
    if (low == high):
        b[pos] = a[high]
        return
     
    mid = (high + low) // 2
     
    # Left subtree
    tree(low, mid, 2 * pos + 1, b, a, n)
     
    # Right subtree
    tree(mid + 1, high, 2 * pos + 2, b, a, n)
     
    # Merge the maximum
    b[pos] = max(b[2 * pos + 1], b[2 * pos + 2])
 
# Function that returns the maximum in range L and R
def rangemax(s, e, low, high, pos, b, a, n):
     
    # Complete overlap
    if (low <= s and high >= e):
        return b[pos]
         
    # Out of range completely
    if (e < low or s > high):
        return -(2**32)
     
    mid = (s + e) // 2
     
    # Find maximum in left and right subtrees
    left = rangemax(s, mid, low, high, 2 * pos + 1, b, a, n)
    right = rangemax(mid + 1, e, low, high, 2 * pos + 2, b, a, n)
     
    # Return the maximum of both
    return max(left, right)
 
# Function that solves a query
def solveQuery(l, r, k, n, a, b, prefix):
     
    # If there are ko
    if (r - l > k):
        return -1
     
    # Find maximum in range L and R
    maximum = rangemax(0, n - 1, l, r, 0, b, a, n)
     
    # If maximum is 0
    if (maximum < 0):
        maximum = 0
     
    # Find the prefix sum
    rangesum = prefix[r]
     
    # If not first element
    if (l > 0):
        rangesum -= prefix[l - 1]
         
    # Get the answer
    answer = rangesum + (k - (r - l)) * maximum
    return answer
 
# Function that solves the queries
def solveQueries( n, a, b, prefix, queries, q):
     
    # Solve all the queries
    for i in range(q):
        ans = solveQuery(queries[i][0], queries[i][1],
                        queries[i][2], n, a, b, prefix)
        if (ans != -1):
            print(ans)
        else:
            print("No")
     
# Function to find the prefix sum
def findPrefixSum( prefix, a, n):
    prefix[0] = a[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + a[i]
 
# Driver code
a = [1, 3, 2, -4, -5 ]
n = len(a)
 
# Array for segment tree
b = [0]*(5 * n)
 
# Create segment tree
tree(0, n - 1, 0, b, a, n)
 
prefix = [0]*n
 
# Fill prefix sum array
findPrefixSum(prefix, a, n)
 
# Queries
queries= [[0, 2, 2],[0, 2, 4],[3, 4, 1],[0, 4, 2]]
 
q = len(queries)
solveQueries(n, a, b, prefix, queries, q)
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# program to implement
// the above approach
using System;
 
class GFG
{
 
// Function to create the tree
static void tree(int low, int high, int pos,
                    int []b, int []a, int n)
{
    // Leaf nodes
    if (low == high)
    {
        b[pos] = a[high];
        return;
    }
    int mid = (high + low) / 2;
 
    // Left subtree
    tree(low, mid, 2 * pos + 1, b, a, n);
 
    // Right subtree
    tree(mid + 1, high, 2 * pos + 2, b, a, n);
 
    // Merge the maximum
    b[pos] = Math.Max(b[2 * pos + 1], b[2 * pos + 2]);
}
 
// Function that returns the maximum in range L and R
static int rangemax(int s, int e, int low, int high,
            int pos, int []b, int []a, int n)
{
    // Complete overlap
    if (low <= s && high >= e)
        return b[pos];
 
    // Out of range completely
    if (e < low || s > high)
        return int.MinValue;
    int mid = (s + e) / 2;
 
    // Find maximum in left and right subtrees
    int left = rangemax(s, mid, low, high,
                        2 * pos + 1, b, a, n);
    int right = rangemax(mid + 1, e, low, high,
                        2 * pos + 2, b, a, n);
 
    // Return the maximum of both
    return Math.Max(left, right);
}
 
// Function that solves a query
static int solveQuery(int l, int r, int k, int n, int []a,
                                    int []b, int []prefix)
{
 
    // If there are ko
    if (r - l > k)
        return -1;
 
    // Find maximum in range L and R
    int maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
 
    // If maximum is 0
    if (maximum < 0)
        maximum = 0;
 
    // Find the prefix sum
    int rangesum = prefix[r];
 
    // If not first element
    if (l > 0)
        rangesum -= prefix[l - 1];
 
    // Get the answer
    int answer = rangesum + (k - (r - l)) * maximum;
 
    return answer;
}
 
// Function that solves the queries
static void solveQueries(int n, int []a, int []b,
                int []prefix, int [,]queries, int q)
{
 
    // Solve all the queries
    for (int i = 0; i < q; i++)
    {
        int ans = solveQuery(queries[i,0], queries[i,1],
                            queries[i,2], n, a, b, prefix);
        if (ans != -1)
            Console.WriteLine(ans);
        else
            Console.WriteLine("No" );
    }
}
 
// Function to find the prefix sum
static void findPrefixSum(int []prefix, int []a, int n)
{
    prefix[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 3, 2, -4, -5 };
    int n = a.Length;
 
    // Array for segment tree
    int []b = new int[5 * n];
 
    // Create segment tree
    tree(0, n - 1, 0, b, a, n);
 
    int []prefix = new int[n];
 
    // Fill prefix sum array
    findPrefixSum(prefix, a, n);
 
    // Queries
    int [,]queries = { { 0, 2, 2 },
                        { 0, 2, 4 },
                        { 3, 4, 1 },
                        { 0, 4, 2 } };
 
    int q = queries.GetLength(0);
    solveQueries(n, a, b, prefix, queries, q);
 
}
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript implementation of the approach
 
// Function to create the tree
function tree(low,high,pos,b,a,n)
{
    // Leaf nodes
    if (low == high)
    {
        b[pos] = a[high];
        return;
    }
    let mid = Math.floor((high + low) / 2);
   
    // Left subtree
    tree(low, mid, 2 * pos + 1, b, a, n);
   
    // Right subtree
    tree(mid + 1, high, 2 * pos + 2, b, a, n);
   
    // Merge the maximum
    b[pos] = Math.max(b[2 * pos + 1], b[2 * pos + 2]);
}
 
// Function that returns the maximum in range L and R
function rangemax(s,e,low,high,pos,b,a,n)
{
    // Complete overlap
    if (low <= s && high >= e)
        return b[pos];
   
    // Out of range completely
    if (e < low || s > high)
        return Number.MIN_VALUE;
    let mid = Math.floor((s + e) / 2);
   
    // Find maximum in left and right subtrees
    let left = rangemax(s, mid, low, high,
                        2 * pos + 1, b, a, n);
    let right = rangemax(mid + 1, e, low, high,
                        2 * pos + 2, b, a, n);
   
    // Return the maximum of both
    return Math.max(left, right);
}
 
// Function that solves a query
function solveQuery(l,r,k,n,a,b,prefix)
{
    // If there are ko
    if (r - l > k)
        return -1;
   
    // Find maximum in range L and R
    let maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
   
    // If maximum is 0
    if (maximum < 0)
        maximum = 0;
   
    // Find the prefix sum
    let rangesum = prefix[r];
   
    // If not first element
    if (l > 0)
        rangesum -= prefix[l - 1];
   
    // Get the answer
    let answer = rangesum + (k - (r - l)) * maximum;
   
    return answer;
}
 
// Function that solves the queries
function solveQueries(n,a,b,prefix,queries,q)
{
    // Solve all the queries
    for (let i = 0; i < q; i++)
    {
        let ans = solveQuery(queries[i][0], queries[i][1],
                            queries[i][2], n, a, b, prefix);
        if (ans != -1)
            document.write(ans+"<br>");
        else
            document.write("No<br>" );
    }
}
 
// Function to find the prefix sum
function findPrefixSum(prefix,a,n)
{
    prefix[0] = a[0];
    for (let i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }
}
 
// Driver code
let a=[1, 3, 2, -4, -5];
let n = a.length;
   
// Array for segment tree
let b = new Array(5 * n);
 
// Create segment tree
tree(0, n - 1, 0, b, a, n);
 
let prefix = new Array(n);
 
// Fill prefix sum array
findPrefixSum(prefix, a, n);
 
// Queries
let queries = [[ 0, 2, 2 ],
[ 0, 2, 4 ],
[ 3, 4, 1 ],
[ 0, 4, 2 ] ];
 
let q = queries.length;
solveQueries(n, a, b, prefix, queries, q);
 
// This code is contributed by rag2127
 
</script>
Producción: 

6
12
-9
No

 

Complejidad de tiempo: O(Log N) por consulta. 
Espacio Auxiliar: O(N log N)
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *