Dadas dos arrays, A[] y B[], cada una de longitud N , donde A[i] y B[i] son los precios del i- ésimo artículo cuando se vende en el mercado A y el mercado B , respectivamente. La tarea es maximizar el perfil de venta de todos los artículos N , pero hay una trampa: si fue al mercado B , entonces no puede regresar. Por ejemplo, si vende los primeros k artículos en el mercado A y tiene que vender el resto de artículos en el mercado B.
Ejemplos:
Entrada: A[] = {2, 3, 2}, B[] = {10, 3, 40}
Salida: 53
Vender todos los artículos en el mercado B para
maximizar la ganancia, es decir (10 + 3 + 40) = 53.Entrada: A[] = {7, 5, 3, 4}, B[] = {2, 3, 1, 3}
Salida: 19
Acercarse:
- Cree una array de suma de prefijos preA[] donde preA[i] almacenará la ganancia cuando los artículos A[0… i ] se vendan en el mercado A.
- Cree una array de suma de sufijos suffB[] donde suffB[i] almacenará la ganancia cuando el artículo B[i…n-1] se venda en el mercado B .
- Ahora el problema se reduce a encontrar un índice i tal que (preA[i] + suffB[i + 1]) sea el máximo.
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 calculate max profit
int maxProfit(int profitA[], int profitB[], int n)
{
// Prefix sum array for profitA[]
int preSum[n];
preSum[0] = profitA[0];
for (int i = 1; i < n; i++) {
preSum[i] = preSum[i - 1] + profitA[i];
}
// Suffix sum array for profitB[]
int suffSum[n];
suffSum[n - 1] = profitB[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffSum[i] = suffSum[i + 1] + profitB[i];
}
// If all the items are sold in market A
int res = preSum[n - 1];
// Find the maximum profit when the first i
// items are sold in market A and the
// rest of the items are sold in market
// B for all possible values of i
for (int i = 1; i < n - 1; i++) {
res = max(res, preSum[i] + suffSum[i + 1]);
}
// If all the items are sold in market B
res = max(res, suffSum[0]);
return res;
}
// Driver code
int main()
{
int profitA[] = { 2, 3, 2 };
int profitB[] = { 10, 30, 40 };
int n = sizeof(profitA) / sizeof(int);
// Function to calculate max profit
cout << maxProfit(profitA, profitB, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to calculate max profit
static int maxProfit(int profitA[], int profitB[], int n)
{
// Prefix sum array for profitA[]
int preSum[] = new int[n];
preSum[0] = profitA[0];
for (int i = 1; i < n; i++)
{
preSum[i] = preSum[i - 1] + profitA[i];
}
// Suffix sum array for profitB[]
int suffSum[] = new int[n];
suffSum[n - 1] = profitB[n - 1];
for (int i = n - 2; i >= 0; i--)
{
suffSum[i] = suffSum[i + 1] + profitB[i];
}
// If all the items are sold in market A
int res = preSum[n - 1];
// Find the maximum profit when the first i
// items are sold in market A and the
// rest of the items are sold in market
// B for all possible values of i
for (int i = 1; i < n - 1; i++)
{
res = Math.max(res, preSum[i] + suffSum[i + 1]);
}
// If all the items are sold in market B
res = Math.max(res, suffSum[0]);
return res;
}
// Driver code
public static void main (String[] args)
{
int profitA[] = { 2, 3, 2 };
int profitB[] = { 10, 30, 40 };
int n = profitA.length;
// Function to calculate max profit
System.out.println(maxProfit(profitA, profitB, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to calculate max profit def maxProfit(profitA, profitB, n) : # Prefix sum array for profitA[] preSum = [0] * n; preSum[0] = profitA[0]; for i in range(1, n) : preSum[i] = preSum[i - 1] + profitA[i]; # Suffix sum array for profitB[] suffSum = [0] * n; suffSum[n - 1] = profitB[n - 1]; for i in range(n - 2, -1, -1) : suffSum[i] = suffSum[i + 1] + profitB[i]; # If all the items are sold in market A res = preSum[n - 1]; # Find the maximum profit when the first i # items are sold in market A and the # rest of the items are sold in market # B for all possible values of i for i in range(1 , n - 1) : res = max(res, preSum[i] + suffSum[i + 1]); # If all the items are sold in market B res = max(res, suffSum[0]); return res; # Driver code if __name__ == "__main__" : profitA = [ 2, 3, 2 ]; profitB = [ 10, 30, 40 ]; n = len(profitA); # Function to calculate max profit print(maxProfit(profitA, profitB, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to calculate max profit
static int maxProfit(int []profitA,
int []profitB, int n)
{
// Prefix sum array for profitA[]
int []preSum = new int[n];
preSum[0] = profitA[0];
for (int i = 1; i < n; i++)
{
preSum[i] = preSum[i - 1] + profitA[i];
}
// Suffix sum array for profitB[]
int []suffSum = new int[n];
suffSum[n - 1] = profitB[n - 1];
for (int i = n - 2; i >= 0; i--)
{
suffSum[i] = suffSum[i + 1] + profitB[i];
}
// If all the items are sold in market A
int res = preSum[n - 1];
// Find the maximum profit when the first i
// items are sold in market A and the
// rest of the items are sold in market
// B for all possible values of i
for (int i = 1; i < n - 1; i++)
{
res = Math.Max(res, preSum[i] +
suffSum[i + 1]);
}
// If all the items are sold in market B
res = Math.Max(res, suffSum[0]);
return res;
}
// Driver code
public static void Main(String[] args)
{
int []profitA = { 2, 3, 2 };
int []profitB = { 10, 30, 40 };
int n = profitA.Length;
// Function to calculate max profit
Console.WriteLine(maxProfit(profitA, profitB, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to calculate max profit
function maxProfit(profitA, profitB, n) {
// Prefix sum array for profitA[]
let preSum = new Array(n);
preSum[0] = profitA[0];
for (let i = 1; i < n; i++) {
preSum[i] = preSum[i - 1] + profitA[i];
}
// Suffix sum array for profitB[]
let suffSum = new Array(n);
suffSum[n - 1] = profitB[n - 1];
for (let i = n - 2; i >= 0; i--) {
suffSum[i] = suffSum[i + 1] + profitB[i];
}
// If all the items are sold in market A
let res = preSum[n - 1];
// Find the maximum profit when the first i
// items are sold in market A and the
// rest of the items are sold in market
// B for all possible values of i
for (let i = 1; i < n - 1; i++) {
res = Math.max(res, preSum[i] + suffSum[i + 1]);
}
// If all the items are sold in market B
res = Math.max(res, suffSum[0]);
return res;
}
// Driver code
let profitA = [2, 3, 2];
let profitB = [10, 30, 40];
let n = profitA.length;
// Function to calculate max profit
document.write(maxProfit(profitA, profitB, n));
</script>
Producción:
80
Implementación alternativa en Python:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int maxProfit(vector<int> a, vector<int> b, int n)
{
// Max profit will be saved here
int maxP = -1;
// loop to check all possible combinations of sales
for (int i = 0; i < n + 1; i++) {
// the sum of the profit after the sale
// for products 0 to i in market A
int sumA = 0;
for (int j = 0; j < min(i, (int)a.size()); j++)
sumA += a[j];
// the sum of the profit after the sale
// for products i to n in market B
int sumB = 0;
for (int j = i; j < b.size(); j++)
sumB += b[j];
// Replace the value of Max Profit with a
// bigger value among maxP and sumA+sumB
maxP = max(maxP, sumA + sumB);
}
// Return the value of Max Profit
return maxP;
}
// Driver Program11111111111111111111111
int main()
{
vector<int> a = { 2, 3, 2 };
vector<int> b = { 10, 30, 40 };
cout << maxProfit(a, b, 4);
return 0;
}
// This code is contributed by pankajsharmagfg.
Java
// Java implementation of the approach
class GFG {
static int maxProfit(int[] a, int[] b, int n)
{
// Max profit will be saved here
int maxP = -1;
// loop to check all possible combinations of sales
for (int i = 0; i < n + 1; i++) {
// the sum of the profit after the sale
// for products 0 to i in market A
int sumA = 0;
for (int j = 0; j < Math.min(i, a.length); j++)
sumA += a[j];
// the sum of the profit after the sale
// for products i to n in market B
int sumB = 0;
for (int j = i; j < b.length; j++)
sumB += b[j];
// Replace the value of Max Profit with a
// bigger value among maxP and sumA+sumB
maxP = Math.max(maxP, sumA + sumB);
}
// Return the value of Max Profit
return maxP;
}
// Driver Program
public static void main(String args[])
{
int[] a = { 2, 3, 2 };
int[] b = { 10, 30, 40 };
System.out.println(maxProfit(a, b, 4));
}
}
// This code is contributed by Lovely Jain
Python3
# Python3 implementation of the approach def maxProfit (a, b, n): # Max profit will be saved here maxP = -1 # loop to check all possible combinations of sales for i in range(0, n+1): # the sum of the profit after the sale # for products 0 to i in market A sumA = sum(a[:i]) # the sum of the profit after the sale # for products i to n in market B sumB = sum(b[i:]) # Replace the value of Max Profit with a # bigger value among maxP and sumA+sumB maxP = max(maxP, sumA+sumB) # Return the value of Max Profit return maxP # Driver Program if __name__ == "__main__" : a = [2, 3, 2] b = [10, 30, 40] print(maxProfit(a, b, 4)) # This code is contributed by aman_malhotra
Javascript
<script>
// JavaScript implementation of the approach
function maxProfit(a, b, n)
{
// Max profit will be saved here
let maxP = -1;
// loop to check all possible combinations of sales
for (let i = 0; i < n + 1; i++) {
// the sum of the profit after the sale
// for products 0 to i in market A
let sumA = 0;
for (let j = 0; j < Math.min(i, a.length); j++)
sumA += a[j];
// the sum of the profit after the sale
// for products i to n in market B
let sumB = 0;
for (let j = i; j < b.length; j++)
sumB += b[j];
// Replace the value of Max Profit with a
// bigger value among maxP and sumA+sumB
maxP = Math.max(maxP, sumA + sumB);
}
// Return the value of Max Profit
return maxP;
}
// Driver Program
let a = [ 2, 3, 2 ];
let b = [ 10, 30, 40 ];
document.write(maxProfit(a, b, 4));
// This code is contributed by shinjanpatra
</script>
Producción:
80
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)