Dados dos arreglos S1 y S2 que contienen N y M enteros, y un entero K , la tarea es encontrar el número máximo de enteros que se pueden eliminar del final de cualquiera de los arreglos dados, de modo que la suma de los elementos eliminados sea menor o igual a k _
Ejemplo:
Entrada: S1[] = {1, 2, 3}, S2[] = {1, 2, 4}, K = 10
Salida: 5
Explicación: Todos los elementos de S1, es decir, {1, 2, 3} y dos los elementos de S2, es decir, {1, 2}, se pueden eliminar de las arrays dadas ya que su suma es 9, que es menor que 10. Por lo tanto, el número de enteros que se pueden eliminar es 5, que es el máximo posible.Entrada: S1[] = {12, 21, 102}, S2[] = {167, 244, 377, 56, 235, 269, 23}, K = 1000
Salida: 7
Enfoque: el enfoque anterior se puede resolver con la ayuda de un enfoque codicioso . La idea es considerar las arrays dadas como pilas (ya que solo el elemento más extremo puede eliminarse de cualquier array). Verifique todas las posibles secuencias válidas de operaciones utilizando un enfoque de dos puntos . A continuación se detallan los pasos a seguir:
- Primero, verifique cuántos números de S1 se pueden obtener considerando que S2 no existe.
- Ahora, la respuesta actual obtenida en el paso 1 se almacena como la respuesta final.
- Ahora comience a atravesar S2 y siga insertando los elementos en el conjunto de enteros eliminados. Si la suma de los elementos eliminados excede K en cualquier punto, elimine los enteros de S1 que se incluyen desde el último hasta que la suma sea menor o igual a K .
- Actualice la respuesta final de acuerdo con la respuesta actual en cada paso, que en realidad proporciona todas las secuencias de operaciones válidas posibles.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return max profit
// from both stacks given as input
int Max_profit_maximisation(int Stack1[], int Stack2[],
int n, int m, int K)
{
// Stores the final answer
int maximum_result = 0;
// Stores the pointer to the
// current window in stack 1
int index_for_Stack1 = 0;
// Stores the pointer to the
// current window in stack 2
int index_for_Stack2;
// Stores sum of current window
int curr_sum = 0;
// Case where snly stack 1
// is considered
while (index_for_Stack1 < n
&& curr_sum + Stack1[index_for_Stack1]
< K) {
curr_sum += Stack1[index_for_Stack1];
index_for_Stack1++;
}
// Update answer
maximum_result = index_for_Stack1;
// Traverse Stack 2 and insert
// elements into the current
// window one at a time
while (index_for_Stack2 < m) {
curr_sum += Stack2[index_for_Stack2];
index_for_Stack2++;
// curr_sum after removing
// last elements from Stack1
while (curr_sum > K
&& index_for_Stack1 > 0) {
index_for_Stack1--;
curr_sum -= Stack1[index_for_Stack1];
}
// Updating the answer
maximum_result
= max(maximum_result,
index_for_Stack1
+ index_for_Stack2);
}
// Return Answer
return maximum_result;
}
// Driver code
int main()
{
int S1[] = { 12, 21, 102 };
int S2[] = { 167, 244, 377, 56,
235, 269, 23 };
int N = 3;
int M = 7;
int K = 1000;
cout << Max_profit_maximisation(S1, S2, N, M, K);
return 0;
}
Java
// Java program of the above approach
import java.util.*;
class GFG{
// Function to return max profit
// from both stacks given as input
static int Max_profit_maximisation(int Stack1[], int Stack2[],
int n, int m, int K)
{
// Stores the final answer
int maximum_result = 0;
// Stores the pointer to the
// current window in stack 1
int index_for_Stack1 =0;
// Stores the pointer to the
// current window in stack 2
int index_for_Stack2=Integer.MAX_VALUE;
// Stores sum of current window
int curr_sum = 0;
// Case where snly stack 1
// is considered
while (index_for_Stack1 < n
&& curr_sum + Stack1[index_for_Stack1]
< K) {
curr_sum += Stack1[index_for_Stack1];
index_for_Stack1++;
}
// Update answer
maximum_result = index_for_Stack1;
// Traverse Stack 2 and insert
// elements into the current
// window one at a time
while (index_for_Stack2 < m) {
curr_sum += Stack2[index_for_Stack2];
index_for_Stack2++;
// curr_sum after removing
// last elements from Stack1
while (curr_sum > K
&& index_for_Stack1 > 0) {
index_for_Stack1--;
curr_sum -= Stack1[index_for_Stack1];
}
// Updating the answer
maximum_result
= Math.max(maximum_result,
index_for_Stack1
+ index_for_Stack2);
}
// Return Answer
return maximum_result;
}
// Driver code
public static void main(String[] args)
{
int S1[] = { 12, 21, 102 };
int S2[] = { 167, 244, 377, 56,
235, 269, 23 };
int N = 3;
int M = 7;
int K = 1000;
System.out.print(Max_profit_maximisation(S1, S2, N, M, K));
}
}
// This code is contributed by shikhasingrajput
Python
# Python program of the above approach # Function to return max profit # from both stacks given as input def Max_profit_maximisation(Stack1, Stack2, n, m, K): # Stores the final answer maximum_result = 0 # Stores the pointer to the # current window in stack 1 index_for_Stack1 = 0 # Stores the pointer to the # current window in stack 2 index_for_Stack2 = 100**100 # Stores sum of current window curr_sum = 0 # Case where snly stack 1 # is considered while (index_for_Stack1 < n and curr_sum + Stack1[index_for_Stack1] < K): curr_sum += Stack1[index_for_Stack1] index_for_Stack1 += 1 # Update answer maximum_result = index_for_Stack1 # Traverse Stack 2 and insert # elements into the current # window one at a time while (index_for_Stack2 < m) : curr_sum += Stack2[index_for_Stack2] index_for_Stack2 += 1 # curr_sum after removing # last elements from Stack1 while (curr_sum > K and index_for_Stack1 > 0): index_for_Stack1 -= 1 curr_sum -= Stack1[index_for_Stack1] # Updating the answer maximum_result = max(maximum_result, index_for_Stack1 + index_for_Stack2) # Return Answer return maximum_result # Driver Code if __name__ == '__main__': S1 = [ 12, 21, 102 ]; S2 = [ 167, 244, 377, 56, 235, 269, 23 ]; N = 3; M = 7; K = 1000; print(Max_profit_maximisation(S1, S2, N, M, K)) # This code is contributed by Samim Hossain Mondal.
C#
// C# program of the above approach
using System;
class GFG{
// Function to return max profit
// from both stacks given as input
static int Max_profit_maximisation(int []Stack1, int []Stack2,
int n, int m, int K)
{
// Stores the readonly answer
int maximum_result = 0;
// Stores the pointer to the
// current window in stack 1
int index_for_Stack1 =0;
// Stores the pointer to the
// current window in stack 2
int index_for_Stack2=int.MaxValue;
// Stores sum of current window
int curr_sum = 0;
// Case where snly stack 1
// is considered
while (index_for_Stack1 < n &&
curr_sum + Stack1[index_for_Stack1] < K)
{
curr_sum += Stack1[index_for_Stack1];
index_for_Stack1++;
}
// Update answer
maximum_result = index_for_Stack1;
// Traverse Stack 2 and insert
// elements into the current
// window one at a time
while (index_for_Stack2 < m)
{
curr_sum += Stack2[index_for_Stack2];
index_for_Stack2++;
// curr_sum after removing
// last elements from Stack1
while (curr_sum > K && index_for_Stack1 > 0)
{
index_for_Stack1--;
curr_sum -= Stack1[index_for_Stack1];
}
// Updating the answer
maximum_result = Math.Max(maximum_result,
index_for_Stack1 +
index_for_Stack2);
}
// Return Answer
return maximum_result;
}
// Driver code
public static void Main(String[] args)
{
int []S1 = { 12, 21, 102 };
int []S2 = { 167, 244, 377, 56,
235, 269, 23 };
int N = 3;
int M = 7;
int K = 1000;
Console.Write(Max_profit_maximisation(S1, S2, N, M, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to return max profit
// from both stacks given as input
function Max_profit_maximisation(Stack1, Stack2,
n, m, K) {
// Stores the final answer
let maximum_result = 0;
// Stores the pointer to the
// current window in stack 1
let index_for_Stack1 = 0;
// Stores the pointer to the
// current window in stack 2
let index_for_Stack2;
// Stores sum of current window
let curr_sum = 0;
// Case where snly stack 1
// is considered
while (index_for_Stack1 < n
&& curr_sum + Stack1[index_for_Stack1]
< K) {
curr_sum += Stack1[index_for_Stack1];
index_for_Stack1++;
}
// Update answer
maximum_result = index_for_Stack1;
// Traverse Stack 2 and insert
// elements into the current
// window one at a time
while (index_for_Stack2 < m) {
curr_sum += Stack2[index_for_Stack2];
index_for_Stack2++;
// curr_sum after removing
// last elements from Stack1
while (curr_sum > K
&& index_for_Stack1 > 0) {
index_for_Stack1--;
curr_sum -= Stack1[index_for_Stack1];
}
// Updating the answer
maximum_result
= Math.max(maximum_result,
index_for_Stack1
+ index_for_Stack2);
}
// Return Answer
return maximum_result;
}
// Driver code
let S1 = [12, 21, 102];
let S2 = [167, 244, 377, 56,
235, 269, 23];
let N = 3;
let M = 7;
let K = 1000;
document.write(Max_profit_maximisation(S1, S2, N, M, K));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal : O(N+M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por agrlmuskan2000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA