Given two arrays, A[] and B[] each of length N where A[i] and B[i] are the prices of the ith 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> |
80
Â
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> |
80
Â
Time Complexity : O(N)
Auxiliary Space : Â O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!