Maximum profit by selling N items at two markets

0 0 9 minutes read

Given two arrays, A[] and B[] each of length N where A[i] and B[i] are the prices of the i^th item when sold in market A and market B respectively. The task is to maximize the profile of selling all the N items, but there is a catch: if you went to market B then you can not return. For example, if you sell the first k items in market A and you have to sell the rest of the items in market B.
Examples:

Input: A[] = {2, 3, 2}, B[] = {10, 3, 40}
Output: 53
Sell all the items in market B in order to
maximize the profit i.e. (10 + 3 + 40) = 53.

Input: A[] = {7, 5, 3, 4}, B[] = {2, 3, 1, 3}
Output: 19

Approach:

Create a prefix sum array preA[] where preA[i] will store the profit when the items A[0…i] are sold in market A.
Create a suffix sum array suffB[] where suffB[i] will store the profit when item B[i…n-1] is sold in market B.
Now the problem is reduced to finding an index i such that (preA[i] + suffB[i + 1]) is the maximum.

Below is the implementation of the above approach:

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>

Output:

Time Complexity: O(n)
Auxiliary Space: O(n)

Alternate Implementation:

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

C#

// Include namespace system
using System;
 
// C# implementation of the approach
public class GFG
{
    public static int maxProfit(int[] a, int[] b, int n)
    {
        // Max profit will be saved here
        var 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
            var 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
            var 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};
        Console.WriteLine(GFG.maxProfit(a, b, 4));
    }
}
 
// This code is contributed by sourabhdalal0001.

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>

Output:

Time Complexity : O(N)
Auxiliary Space : O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!